Submission #1612028
Source Code Expand
#include<cstdio> #include<cstring> #include<cstdlib> using namespace std; const int maxn=100100; int f1[maxn],f2[maxn]; int cnt1[maxn],cnt2[maxn]; int beg[maxn],nex[maxn<<1],tto[maxn<<1],e; void putin(int s,int t){ tto[++e]=t; nex[e]=beg[s]; beg[s]=e; } int val[maxn]; struct node{ int s,t; }w[maxn<<1]; int num; void setgraph(){ memset(beg,0,sizeof(beg)); e=0; } int dfs(int u){ int v=-1,t; if(cnt1[u]&1) v=u; for(int i=beg[u];i;i=nex[i]){ t=dfs(tto[i]); if(v==-1) v=t; else w[++num]=(node){v,t},v=-1; } if(v==-1){ printf("IMPOSSIBLE\n"); exit(0); } return v; } void color(int u,int v){ val[u]=v; for(int i=beg[u];i;i=nex[i]){ if(val[tto[i]]){ if(val[tto[i]]==val[u]){ printf("IMPOSSIBLE\n"); exit(0); } } else color(tto[i],-v); } } int main(){ // freopen("F.in","r",stdin); // freopen("F.out","w",stdout); int n,rt; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&f1[i]); if(f1[i]>0) cnt1[f1[i]]++; } for(int i=1;i<=n;i++){ scanf("%d",&f2[i]); if(f2[i]>0) cnt2[f2[i]]++; } for(int i=1;i<=n;i++) { cnt1[i]=!(cnt1[i]&1); cnt2[i]=!(cnt2[i]&1); if(cnt1[i]!=cnt2[i]){ printf("IMPOSSIBLE\n"); return 0; } } setgraph(); for(int i=1;i<=n;i++) { if(f1[i]>0) putin(f1[i],i); else rt=i; } dfs(rt); setgraph(); for(int i=1;i<=n;i++) { if(f2[i]>0) putin(f2[i],i); else rt=i; } dfs(rt); setgraph(); for(int i=1;i<=num;i++) { putin(w[i].s,w[i].t); putin(w[i].t,w[i].s); } for(int i=1;i<=n;i++) if(!val[i]&&(cnt1[i]&1)) color(i,1); printf("POSSIBLE\n"); for(int i=1;i<=n;i++) printf("%d ",val[i]); printf("\n"); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Two Trees |
User | xzkflowey |
Language | C++14 (GCC 5.4.1) |
Score | 1700 |
Code Size | 1758 Byte |
Status | AC |
Exec Time | 42 ms |
Memory | 7424 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:54:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&n); ^ ./Main.cpp:56:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&f1[i]); ^ ./Main.cpp:60:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&f2[i]); ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1700 / 1700 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_49.txt, subtask_1_50.txt, subtask_1_51.txt, subtask_1_52.txt, subtask_1_53.txt, subtask_1_54.txt, subtask_1_55.txt, subtask_1_56.txt, subtask_1_57.txt, subtask_1_58.txt, subtask_1_59.txt, subtask_1_60.txt, subtask_1_61.txt, subtask_1_62.txt, subtask_1_63.txt, subtask_1_64.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 1 ms | 2176 KB |
sample_02.txt | AC | 1 ms | 2176 KB |
sample_03.txt | AC | 1 ms | 2176 KB |
subtask_1_01.txt | AC | 1 ms | 2176 KB |
subtask_1_02.txt | AC | 1 ms | 2176 KB |
subtask_1_03.txt | AC | 12 ms | 2944 KB |
subtask_1_04.txt | AC | 27 ms | 5376 KB |
subtask_1_05.txt | AC | 18 ms | 3456 KB |
subtask_1_06.txt | AC | 9 ms | 3328 KB |
subtask_1_07.txt | AC | 24 ms | 3840 KB |
subtask_1_08.txt | AC | 11 ms | 2688 KB |
subtask_1_09.txt | AC | 12 ms | 2944 KB |
subtask_1_10.txt | AC | 24 ms | 4864 KB |
subtask_1_11.txt | AC | 5 ms | 2432 KB |
subtask_1_12.txt | AC | 32 ms | 5888 KB |
subtask_1_13.txt | AC | 14 ms | 3072 KB |
subtask_1_14.txt | AC | 5 ms | 2688 KB |
subtask_1_15.txt | AC | 10 ms | 2944 KB |
subtask_1_16.txt | AC | 16 ms | 2944 KB |
subtask_1_17.txt | AC | 10 ms | 2816 KB |
subtask_1_18.txt | AC | 34 ms | 6016 KB |
subtask_1_19.txt | AC | 20 ms | 3584 KB |
subtask_1_20.txt | AC | 38 ms | 6016 KB |
subtask_1_21.txt | AC | 20 ms | 3584 KB |
subtask_1_22.txt | AC | 20 ms | 3584 KB |
subtask_1_23.txt | AC | 38 ms | 6784 KB |
subtask_1_24.txt | AC | 36 ms | 4736 KB |
subtask_1_25.txt | AC | 20 ms | 3328 KB |
subtask_1_26.txt | AC | 20 ms | 3584 KB |
subtask_1_27.txt | AC | 37 ms | 6272 KB |
subtask_1_28.txt | AC | 20 ms | 3584 KB |
subtask_1_29.txt | AC | 37 ms | 5888 KB |
subtask_1_30.txt | AC | 20 ms | 3584 KB |
subtask_1_31.txt | AC | 20 ms | 3584 KB |
subtask_1_32.txt | AC | 38 ms | 6144 KB |
subtask_1_33.txt | AC | 36 ms | 4736 KB |
subtask_1_34.txt | AC | 20 ms | 3072 KB |
subtask_1_35.txt | AC | 20 ms | 3584 KB |
subtask_1_36.txt | AC | 37 ms | 6272 KB |
subtask_1_37.txt | AC | 38 ms | 6144 KB |
subtask_1_38.txt | AC | 38 ms | 6272 KB |
subtask_1_39.txt | AC | 38 ms | 6528 KB |
subtask_1_40.txt | AC | 42 ms | 6144 KB |
subtask_1_41.txt | AC | 38 ms | 6144 KB |
subtask_1_42.txt | AC | 30 ms | 5248 KB |
subtask_1_43.txt | AC | 37 ms | 7040 KB |
subtask_1_44.txt | AC | 37 ms | 6016 KB |
subtask_1_45.txt | AC | 38 ms | 5760 KB |
subtask_1_46.txt | AC | 38 ms | 6528 KB |
subtask_1_47.txt | AC | 38 ms | 6272 KB |
subtask_1_48.txt | AC | 39 ms | 6016 KB |
subtask_1_49.txt | AC | 30 ms | 5504 KB |
subtask_1_50.txt | AC | 39 ms | 6400 KB |
subtask_1_51.txt | AC | 38 ms | 6400 KB |
subtask_1_52.txt | AC | 38 ms | 7296 KB |
subtask_1_53.txt | AC | 38 ms | 6400 KB |
subtask_1_54.txt | AC | 38 ms | 6528 KB |
subtask_1_55.txt | AC | 39 ms | 6784 KB |
subtask_1_56.txt | AC | 30 ms | 5504 KB |
subtask_1_57.txt | AC | 37 ms | 7296 KB |
subtask_1_58.txt | AC | 38 ms | 5888 KB |
subtask_1_59.txt | AC | 38 ms | 6528 KB |
subtask_1_60.txt | AC | 38 ms | 6400 KB |
subtask_1_61.txt | AC | 38 ms | 5888 KB |
subtask_1_62.txt | AC | 38 ms | 5760 KB |
subtask_1_63.txt | AC | 31 ms | 7424 KB |
subtask_1_64.txt | AC | 37 ms | 7296 KB |