Submission #1593181
Source Code Expand
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int N=500010;
//const int N=100;
struct node{
int to,next,id;
};node edge[N*2];
int graph[N],tot;
int c[N],id[N];int vis[N];int sp[N];
int con[N];
int ID;
int rt1,rt2;
void addedge(int i,int x,int y,int id){
edge[i].to=y;edge[i].next=graph[x];graph[x]=i;edge[i].id=id;
}
void dfs(int x){
int i,y,id;
for(i=graph[x];i;i=graph[x]){
y=edge[i].to;id=edge[i].id;
graph[x]=edge[i].next;
if(vis[id]) continue;
if(!sp[id]){c[x]--;c[y]++;}
vis[id]=1;
dfs(y);
}
}
int main(){
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
int i,n,x;
scanf("%d",&n);
rep(i,1,n){
scanf("%d",&x);
if(x==-1){rt1=i;con[i]++;}
else{
ID++;
tot++;addedge(tot,i,x,ID);
tot++;addedge(tot,x,i,ID);
con[i]++;con[x]++;
}
}
rep(i,1,n) if(con[i]&1){
ID++;sp[ID]=1;
tot++;addedge(tot,i,i+n,ID);
tot++;addedge(tot,i+n,i,ID);
}
rep(i,1,n){
scanf("%d",&x);
if(x==-1){rt2=i+n;con[i]++;}
else{
ID++;
tot++;addedge(tot,i+n,x+n,ID);
tot++;addedge(tot,x+n,i+n,ID);
con[i]++;con[x]++;
}
}
ID++;
tot++;addedge(tot,rt1,rt2,ID);
tot++;addedge(tot,rt2,rt1,ID);
rep(i,1,n) if(con[i]&1) {printf("IMPOSSIBLE\n");return 0;}
printf("POSSIBLE\n");
dfs(1);
rep(i,1,n) printf("%d ",c[i]);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Two Trees |
User |
tyc2001 |
Language |
C++14 (GCC 5.4.1) |
Score |
1700 |
Code Size |
1568 Byte |
Status |
AC |
Exec Time |
68 ms |
Memory |
23936 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:38:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:40:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
^
./Main.cpp:55:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
^
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 |
2 ms |
8320 KB |
sample_02.txt |
AC |
1 ms |
4224 KB |
sample_03.txt |
AC |
2 ms |
8320 KB |
subtask_1_01.txt |
AC |
1 ms |
4224 KB |
subtask_1_02.txt |
AC |
1 ms |
4224 KB |
subtask_1_03.txt |
AC |
15 ms |
10624 KB |
subtask_1_04.txt |
AC |
42 ms |
20224 KB |
subtask_1_05.txt |
AC |
22 ms |
12800 KB |
subtask_1_06.txt |
AC |
13 ms |
13696 KB |
subtask_1_07.txt |
AC |
29 ms |
14976 KB |
subtask_1_08.txt |
AC |
12 ms |
10624 KB |
subtask_1_09.txt |
AC |
14 ms |
10624 KB |
subtask_1_10.txt |
AC |
30 ms |
17792 KB |
subtask_1_11.txt |
AC |
6 ms |
8448 KB |
subtask_1_12.txt |
AC |
41 ms |
20864 KB |
subtask_1_13.txt |
AC |
17 ms |
10624 KB |
subtask_1_14.txt |
AC |
7 ms |
11008 KB |
subtask_1_15.txt |
AC |
13 ms |
12672 KB |
subtask_1_16.txt |
AC |
19 ms |
12800 KB |
subtask_1_17.txt |
AC |
12 ms |
10624 KB |
subtask_1_18.txt |
AC |
44 ms |
21248 KB |
subtask_1_19.txt |
AC |
24 ms |
12800 KB |
subtask_1_20.txt |
AC |
50 ms |
21504 KB |
subtask_1_21.txt |
AC |
24 ms |
12800 KB |
subtask_1_22.txt |
AC |
24 ms |
12800 KB |
subtask_1_23.txt |
AC |
49 ms |
21504 KB |
subtask_1_24.txt |
AC |
43 ms |
17280 KB |
subtask_1_25.txt |
AC |
22 ms |
14848 KB |
subtask_1_26.txt |
AC |
23 ms |
12800 KB |
subtask_1_27.txt |
AC |
46 ms |
21632 KB |
subtask_1_28.txt |
AC |
24 ms |
12800 KB |
subtask_1_29.txt |
AC |
50 ms |
21504 KB |
subtask_1_30.txt |
AC |
24 ms |
12800 KB |
subtask_1_31.txt |
AC |
24 ms |
12800 KB |
subtask_1_32.txt |
AC |
49 ms |
21504 KB |
subtask_1_33.txt |
AC |
45 ms |
17280 KB |
subtask_1_34.txt |
AC |
22 ms |
14848 KB |
subtask_1_35.txt |
AC |
23 ms |
12800 KB |
subtask_1_36.txt |
AC |
52 ms |
21632 KB |
subtask_1_37.txt |
AC |
68 ms |
21504 KB |
subtask_1_38.txt |
AC |
49 ms |
21504 KB |
subtask_1_39.txt |
AC |
48 ms |
21504 KB |
subtask_1_40.txt |
AC |
48 ms |
21504 KB |
subtask_1_41.txt |
AC |
49 ms |
21376 KB |
subtask_1_42.txt |
AC |
35 ms |
23936 KB |
subtask_1_43.txt |
AC |
49 ms |
21632 KB |
subtask_1_44.txt |
AC |
49 ms |
21504 KB |
subtask_1_45.txt |
AC |
53 ms |
21504 KB |
subtask_1_46.txt |
AC |
49 ms |
21504 KB |
subtask_1_47.txt |
AC |
50 ms |
21504 KB |
subtask_1_48.txt |
AC |
49 ms |
21376 KB |
subtask_1_49.txt |
AC |
36 ms |
23936 KB |
subtask_1_50.txt |
AC |
46 ms |
21632 KB |
subtask_1_51.txt |
AC |
49 ms |
21504 KB |
subtask_1_52.txt |
AC |
50 ms |
21504 KB |
subtask_1_53.txt |
AC |
51 ms |
21504 KB |
subtask_1_54.txt |
AC |
49 ms |
21504 KB |
subtask_1_55.txt |
AC |
57 ms |
21504 KB |
subtask_1_56.txt |
AC |
35 ms |
23936 KB |
subtask_1_57.txt |
AC |
50 ms |
21632 KB |
subtask_1_58.txt |
AC |
51 ms |
21504 KB |
subtask_1_59.txt |
AC |
50 ms |
21504 KB |
subtask_1_60.txt |
AC |
50 ms |
21504 KB |
subtask_1_61.txt |
AC |
50 ms |
21504 KB |
subtask_1_62.txt |
AC |
50 ms |
21376 KB |
subtask_1_63.txt |
AC |
35 ms |
23936 KB |
subtask_1_64.txt |
AC |
64 ms |
21632 KB |