Submission #3735504
Source Code Expand
#include<cstdio> #include<cctype> const int maxn=1000010; int n; int a[maxn],b[maxn]; int dg[maxn]; struct Edge { int to,id,fl; Edge *ne; }el[maxn],*la[maxn],*st[maxn],*cl=el; int cc; bool vv[maxn]; int ww[maxn],xx[maxn]; int In() { register char c; for(;c=getchar(),c!='-'&&!isdigit(c);); register bool f=c=='-'; register int s=f?0:c-'0'; for(;c=getchar(),isdigit(c);)s=s*10+c-'0'; return f?-s:s; } void ins(register int u,register int v,register int id) { ++cc; *++cl=(Edge){v,id,cc,la[u]},la[u]=cl,++dg[v]; *++cl=(Edge){u,-id,cc,la[v]},la[v]=cl,++dg[u]; } void dfs(int x) { for(Edge *i=la[x];i;i=la[x]) { if(!vv[i->fl]) { if(i->id) i->id>0?ww[i->id]=1:ww[-i->id]=-1; vv[i->fl]=1,la[x]=la[x]->ne,dfs(i->to); } else la[x]=la[x]->ne; } } int main() { n=In(); for(register int i=1;i<=n;++i)a[i]=In(),~a[i]?ins(i,a[i],i):ins(i,0,i); for(register int i=1;i<=n;++i)b[i]=In(),~b[i]?ins(i+n,b[i]+n,0):ins(i+n,0,0); for(register int i=1;i<=n;++i) { if((dg[i]&1)^(dg[i+n]&1)) return puts("IMPOSSBILE"),0; register int z=dg[i]<dg[i+n]?dg[i]:dg[i+n]; for(register int j=1;j<=z;++j)ins(i,i+n,0); } for(register int i=1;i<=n;++i)st[i]=la[i]; dfs(0); for(register int i=1;i<=n;++i) { xx[i]=-ww[i]; for(register Edge *j=st[i];j;j=j->ne)if(j->to&&j->to<=n&&j->to!=a[i]) xx[i]+=ww[j->to]; } puts("POSSBILE"); for(register int i=1;i<=n;++i)printf("%d%c",xx[i]," \n"[i==n]); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Two Trees |
User | LeehWinCing |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1468 Byte |
Status | WA |
Exec Time | 98 ms |
Memory | 43264 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | WA | 4 ms | 16512 KB |
sample_02.txt | WA | 3 ms | 12416 KB |
sample_03.txt | WA | 4 ms | 16512 KB |
subtask_1_01.txt | WA | 3 ms | 12416 KB |
subtask_1_02.txt | WA | 3 ms | 12416 KB |
subtask_1_03.txt | WA | 12 ms | 18560 KB |
subtask_1_04.txt | WA | 50 ms | 35328 KB |
subtask_1_05.txt | WA | 16 ms | 22656 KB |
subtask_1_06.txt | WA | 16 ms | 22144 KB |
subtask_1_07.txt | WA | 46 ms | 33408 KB |
subtask_1_08.txt | WA | 10 ms | 18560 KB |
subtask_1_09.txt | WA | 11 ms | 18560 KB |
subtask_1_10.txt | WA | 46 ms | 34944 KB |
subtask_1_11.txt | WA | 6 ms | 14464 KB |
subtask_1_12.txt | WA | 68 ms | 38272 KB |
subtask_1_13.txt | WA | 12 ms | 20608 KB |
subtask_1_14.txt | WA | 10 ms | 19328 KB |
subtask_1_15.txt | WA | 17 ms | 22912 KB |
subtask_1_16.txt | WA | 14 ms | 22656 KB |
subtask_1_17.txt | WA | 9 ms | 18560 KB |
subtask_1_18.txt | WA | 68 ms | 40704 KB |
subtask_1_19.txt | WA | 19 ms | 22656 KB |
subtask_1_20.txt | WA | 88 ms | 43264 KB |
subtask_1_21.txt | WA | 16 ms | 22656 KB |
subtask_1_22.txt | WA | 19 ms | 24704 KB |
subtask_1_23.txt | WA | 76 ms | 43264 KB |
subtask_1_24.txt | WA | 77 ms | 39808 KB |
subtask_1_25.txt | WA | 17 ms | 24704 KB |
subtask_1_26.txt | WA | 19 ms | 22656 KB |
subtask_1_27.txt | WA | 71 ms | 43264 KB |
subtask_1_28.txt | WA | 18 ms | 22656 KB |
subtask_1_29.txt | WA | 75 ms | 43136 KB |
subtask_1_30.txt | WA | 17 ms | 22656 KB |
subtask_1_31.txt | WA | 17 ms | 22656 KB |
subtask_1_32.txt | WA | 81 ms | 43264 KB |
subtask_1_33.txt | WA | 81 ms | 39808 KB |
subtask_1_34.txt | WA | 17 ms | 24704 KB |
subtask_1_35.txt | WA | 17 ms | 22656 KB |
subtask_1_36.txt | WA | 82 ms | 43264 KB |
subtask_1_37.txt | WA | 80 ms | 43264 KB |
subtask_1_38.txt | WA | 81 ms | 43136 KB |
subtask_1_39.txt | WA | 88 ms | 43136 KB |
subtask_1_40.txt | WA | 94 ms | 43264 KB |
subtask_1_41.txt | WA | 91 ms | 43264 KB |
subtask_1_42.txt | WA | 35 ms | 38272 KB |
subtask_1_43.txt | WA | 74 ms | 43264 KB |
subtask_1_44.txt | WA | 74 ms | 43264 KB |
subtask_1_45.txt | WA | 74 ms | 43136 KB |
subtask_1_46.txt | WA | 79 ms | 43136 KB |
subtask_1_47.txt | WA | 85 ms | 43264 KB |
subtask_1_48.txt | WA | 86 ms | 43264 KB |
subtask_1_49.txt | WA | 35 ms | 38272 KB |
subtask_1_50.txt | WA | 87 ms | 43264 KB |
subtask_1_51.txt | WA | 95 ms | 43136 KB |
subtask_1_52.txt | WA | 94 ms | 43136 KB |
subtask_1_53.txt | WA | 79 ms | 43264 KB |
subtask_1_54.txt | WA | 88 ms | 43136 KB |
subtask_1_55.txt | WA | 78 ms | 43264 KB |
subtask_1_56.txt | WA | 35 ms | 38272 KB |
subtask_1_57.txt | WA | 73 ms | 43264 KB |
subtask_1_58.txt | WA | 98 ms | 43264 KB |
subtask_1_59.txt | WA | 81 ms | 43264 KB |
subtask_1_60.txt | WA | 73 ms | 43136 KB |
subtask_1_61.txt | WA | 80 ms | 43264 KB |
subtask_1_62.txt | WA | 74 ms | 43264 KB |
subtask_1_63.txt | WA | 34 ms | 38272 KB |
subtask_1_64.txt | WA | 70 ms | 43264 KB |