Submission #3862591

Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
int N; long long D[101010];
int size[101010], parent[101010];
map<long long, int> D2I; //Distance-index;
vector<int> child[101010];
void check(bool p)
{
  if(!p)
  {
    puts("-1");
    exit(0);
  }
}
long long dfs(int ind, int height)
{
  long long ans = height;
  for(auto x: child[ind]) ans += dfs(x, height+1);
  return ans;
}
void verify_print()
{
  int root = 0;
  for(int i=1; i<=N; ++i)
  {
    if(parent[i]) child[parent[i]].push_back(i);
    else root = i;
  }
  check(dfs(root, 0) == D[root]);
  for(int i=1; i<=N; ++i)
    if(parent[i])
      printf("%d %d\n", parent[i], i);
  return;
}
int main()
{
  vector<pair<long long, int> > V;
  scanf("%d", &N);
  for(int i=1; i<=N; ++i)
  {
    scanf("%lld", D+i);
    V.emplace_back(D[i], i);
    D2I[D[i]] = i;
  }
  sort(V.rbegin(), V.rend());
  for(auto x: V)
  {
    long long distance; int index; tie(distance, index) = x;
    size[index]++;
    
    if(V[V.size()-1] == x) check(size[index] == N);
    else
    {
      check(size[index] <= (N-1)/2);
      long long pdist = distance - (N-2*size[index]);
      int pind = D2I[pdist]; check(pind != 0);
      parent[index] = pind; size[pind] += size[index];
    }
  }  
  verify_print();
  return 0;
}

Submission Info

Submission Time
Task F - Distance Sums
User HYEA
Language C++14 (GCC 5.4.1)
Score 900
Code Size 1318 Byte
Status
Exec Time 106 ms
Memory 18672 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:38:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
                  ^
./Main.cpp:41:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", D+i);
                       ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt
All 900 / 900 sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 4.txt, 40.txt, 41.txt, 42.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
1.txt 3 ms 2816 KB
10.txt 102 ms 18544 KB
11.txt 65 ms 12016 KB
12.txt 62 ms 12016 KB
13.txt 66 ms 12016 KB
14.txt 100 ms 18544 KB
15.txt 98 ms 18416 KB
16.txt 98 ms 18160 KB
17.txt 98 ms 18160 KB
18.txt 62 ms 12016 KB
19.txt 99 ms 18544 KB
2.txt 3 ms 2688 KB
20.txt 100 ms 18544 KB
21.txt 54 ms 10864 KB
22.txt 100 ms 18416 KB
23.txt 102 ms 18288 KB
24.txt 89 ms 16880 KB
25.txt 61 ms 12016 KB
26.txt 61 ms 11632 KB
27.txt 62 ms 12016 KB
28.txt 61 ms 12016 KB
29.txt 100 ms 18160 KB
3.txt 10 ms 4220 KB
30.txt 102 ms 18288 KB
31.txt 100 ms 17776 KB
32.txt 98 ms 18032 KB
33.txt 84 ms 16752 KB
34.txt 100 ms 18288 KB
35.txt 84 ms 17136 KB
36.txt 83 ms 17392 KB
37.txt 101 ms 18288 KB
38.txt 100 ms 18288 KB
39.txt 104 ms 18416 KB
4.txt 7 ms 3580 KB
40.txt 102 ms 18160 KB
41.txt 106 ms 17648 KB
42.txt 79 ms 15088 KB
5.txt 47 ms 10612 KB
6.txt 101 ms 18672 KB
7.txt 105 ms 18544 KB
8.txt 101 ms 18544 KB
9.txt 104 ms 18544 KB
sample1.txt 2 ms 2560 KB
sample2.txt 2 ms 2560 KB
sample3.txt 2 ms 2560 KB