Submission #9811007
Source Code Expand
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=100005,p=1000000007; int read(){ int f=1,g=0; char ch=getchar(); for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1; for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0'; return f*g; } int n,fl,siz[N],b[N],fa[N]; vector<int> e[N]; ll a[N],f[N],ans[N]; unordered_map<ll,int> h; bool cmp(int x,int y){return a[x]<a[y];} void work(int x){ f[x]=siz[x]-1; for (auto y : e[x]){work(y);f[x]+=f[y];} } void calc(int x,ll s){ ans[x]=f[x]+s+n-siz[x]; for (auto y : e[x]) calc(y,ans[x]-f[y]-siz[y]); } int main(){ n=read(); for (int i=1;i<=n;i++) {scanf("%lld",a+i);h[a[i]]=i;b[i]=i;siz[i]=1;} sort(b+1,b+n+1,cmp); for (int i=n;i>1;i--){ int x=b[i]; fa[x]=h[a[x]+siz[x]-n+siz[x]]; if (!fa[x]){puts("-1");return 0;} siz[fa[x]]+=siz[x]; e[fa[x]].push_back(x); } work(b[1]); calc(b[1],0); for (int i=1;i<=n;i++) if (ans[i]!=a[i]){puts("-1");return 0;} for (int i=2;i<=n;i++) printf("%d %d\n",fa[b[i]],b[i]); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Distance Sums |
User | liji |
Language | C++14 (GCC 5.4.1) |
Score | 900 |
Code Size | 1050 Byte |
Status | AC |
Exec Time | 84 ms |
Memory | 16804 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:28:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] for (int i=1;i<=n;i++) {scanf("%lld",a+i);h[a[i]]=i;b[i]=i;siz[i]=1;} ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 900 / 900 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample1.txt, sample2.txt, sample3.txt |
All | 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 | AC | 3 ms | 3072 KB |
10.txt | AC | 82 ms | 16676 KB |
11.txt | AC | 52 ms | 10276 KB |
12.txt | AC | 44 ms | 8996 KB |
13.txt | AC | 57 ms | 11044 KB |
14.txt | AC | 82 ms | 16804 KB |
15.txt | AC | 83 ms | 16676 KB |
16.txt | AC | 84 ms | 16420 KB |
17.txt | AC | 83 ms | 16420 KB |
18.txt | AC | 46 ms | 9380 KB |
19.txt | AC | 83 ms | 16804 KB |
2.txt | AC | 2 ms | 2944 KB |
20.txt | AC | 81 ms | 16804 KB |
21.txt | AC | 39 ms | 8484 KB |
22.txt | AC | 84 ms | 16676 KB |
23.txt | AC | 83 ms | 16548 KB |
24.txt | AC | 74 ms | 15524 KB |
25.txt | AC | 44 ms | 8996 KB |
26.txt | AC | 45 ms | 9124 KB |
27.txt | AC | 44 ms | 8996 KB |
28.txt | AC | 43 ms | 8740 KB |
29.txt | AC | 82 ms | 16292 KB |
3.txt | AC | 9 ms | 4352 KB |
30.txt | AC | 84 ms | 16548 KB |
31.txt | AC | 82 ms | 15908 KB |
32.txt | AC | 83 ms | 16292 KB |
33.txt | AC | 72 ms | 14884 KB |
34.txt | AC | 83 ms | 16548 KB |
35.txt | AC | 68 ms | 15396 KB |
36.txt | AC | 68 ms | 15652 KB |
37.txt | AC | 83 ms | 16420 KB |
38.txt | AC | 83 ms | 16548 KB |
39.txt | AC | 84 ms | 16676 KB |
4.txt | AC | 6 ms | 3712 KB |
40.txt | AC | 84 ms | 16292 KB |
41.txt | AC | 83 ms | 15908 KB |
42.txt | AC | 66 ms | 14116 KB |
5.txt | AC | 40 ms | 9996 KB |
6.txt | AC | 84 ms | 16804 KB |
7.txt | AC | 83 ms | 16804 KB |
8.txt | AC | 83 ms | 16804 KB |
9.txt | AC | 84 ms | 16804 KB |
sample1.txt | AC | 2 ms | 2944 KB |
sample2.txt | AC | 2 ms | 2944 KB |
sample3.txt | AC | 2 ms | 2944 KB |