Submission #6597099


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
int read(){
    int c=0,nx,sign=1;
    do{
        nx=getchar()-'0';
        if(nx=='-'-'0')
            sign=-1;
    }while(nx<0 or nx>9);
    while(nx>=0 and nx<=9){
        c=c*10+nx;
        nx=getchar()-'0';
    }
    return sign*c;
}
template<typename T>
void write(T x){
	if(x<0)
		putchar('-'),x=-x;
	if(x>9)
		write(x/10);
	putchar(x%10+48);
}
const int  N=5e5+100,M=6*N;
int head[N],next[M],ver[M];
inline void addEdge(int u,int v){
    static int now=1;
    ++now;
    next[now]=head[u];
    ver[now]=v;
    head[u]=now;
}
int n;
int cnt[N];
int fa[N],vis[N];
int ans[N];
int c[M],top;
void dfs(int u){
    for(int i=head[u];i;i=next[i]){
        if(vis[i])
            continue;
        vis[i]=vis[i^1]=1;
        head[u]=next[i];
        dfs(ver[i]);
    }
    c[top++]=u;
}
int main(){
    n=read();
    int u,v,s=2*n+1;
    for(int i=1;i<=n;i++){
        u=read();
        if(u==-1)
            u=s;
        cnt[u]++;
        addEdge(u,i);
        addEdge(i,u);
    }
    for(int i=1;i<=n;i++){
        u=read();
        if(u==-1)
            u=s;
        else
            u=s-u;
        ++cnt[u];
        v=s-i;
        addEdge(u,v);
        addEdge(v,u);
    }
    
    for(int i=1;i<=2*n;i++)
        cnt[i]=!(cnt[i]&1);
    cnt[s]=0;
    
    for(int i=1;i<=n;i++){
        if(cnt[i]^cnt[s-i]){
            puts("IMPOSSIBLE");
            return 0;
        }
        if(cnt[i])
            addEdge(i,s-i),addEdge(s-i,i);
    }
    
    dfs(n/2);
    for(int i=top-1;i>=1;i--){
    	if(c[i]==s-c[i-1]){
    		int u=c[i];
    		if(u<=n)
    			ans[u]=1;
    		else
    			ans[s-u]=-1;
        }
    }
    
    puts("POSSIBLE");
    for(int i=1;i<=n;i++)
        write(ans[i]),putchar(' ');
    putchar('\n');
}

Submission Info

Submission Time
Task F - Two Trees
User luogu_bot4
Language C++ (GCC 5.4.1)
Score 0
Code Size 1870 Byte
Status TLE
Exec Time 2104 ms
Memory 29696 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1700
Status
AC × 3
AC × 66
TLE × 4
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 4 ms 12544 KB
sample_02.txt AC 3 ms 8448 KB
sample_03.txt AC 3 ms 12544 KB
subtask_1_01.txt AC 3 ms 8448 KB
subtask_1_02.txt AC 3 ms 8448 KB
subtask_1_03.txt AC 9 ms 10880 KB
subtask_1_04.txt AC 31 ms 26496 KB
subtask_1_05.txt AC 13 ms 11136 KB
subtask_1_06.txt AC 11 ms 15104 KB
subtask_1_07.txt AC 21 ms 18048 KB
subtask_1_08.txt AC 8 ms 10880 KB
subtask_1_09.txt AC 9 ms 8832 KB
subtask_1_10.txt AC 621 ms 23680 KB
subtask_1_11.txt AC 5 ms 8576 KB
subtask_1_12.txt AC 36 ms 28032 KB
subtask_1_13.txt AC 10 ms 11008 KB
subtask_1_14.txt AC 7 ms 13824 KB
subtask_1_15.txt AC 10 ms 13184 KB
subtask_1_16.txt AC 12 ms 13184 KB
subtask_1_17.txt AC 8 ms 8832 KB
subtask_1_18.txt AC 1229 ms 28672 KB
subtask_1_19.txt AC 14 ms 13312 KB
subtask_1_20.txt AC 41 ms 29568 KB
subtask_1_21.txt AC 14 ms 13312 KB
subtask_1_22.txt AC 14 ms 13312 KB
subtask_1_23.txt AC 41 ms 29312 KB
subtask_1_24.txt AC 30 ms 20736 KB
subtask_1_25.txt AC 14 ms 13312 KB
subtask_1_26.txt AC 14 ms 13312 KB
subtask_1_27.txt AC 1474 ms 29696 KB
subtask_1_28.txt AC 14 ms 13312 KB
subtask_1_29.txt AC 41 ms 29568 KB
subtask_1_30.txt AC 14 ms 13312 KB
subtask_1_31.txt AC 14 ms 13312 KB
subtask_1_32.txt AC 41 ms 29440 KB
subtask_1_33.txt AC 30 ms 20736 KB
subtask_1_34.txt AC 15 ms 13312 KB
subtask_1_35.txt AC 14 ms 13312 KB
subtask_1_36.txt AC 1466 ms 29696 KB
subtask_1_37.txt AC 41 ms 29568 KB
subtask_1_38.txt AC 41 ms 29440 KB
subtask_1_39.txt AC 43 ms 29440 KB
subtask_1_40.txt AC 43 ms 29440 KB
subtask_1_41.txt AC 40 ms 29184 KB
subtask_1_42.txt TLE 2104 ms 27136 KB
subtask_1_43.txt AC 1471 ms 29696 KB
subtask_1_44.txt AC 42 ms 29440 KB
subtask_1_45.txt AC 42 ms 29440 KB
subtask_1_46.txt AC 42 ms 29568 KB
subtask_1_47.txt AC 41 ms 29440 KB
subtask_1_48.txt AC 40 ms 29184 KB
subtask_1_49.txt TLE 2104 ms 27136 KB
subtask_1_50.txt AC 1474 ms 29696 KB
subtask_1_51.txt AC 41 ms 29440 KB
subtask_1_52.txt AC 41 ms 29440 KB
subtask_1_53.txt AC 41 ms 29440 KB
subtask_1_54.txt AC 41 ms 29440 KB
subtask_1_55.txt AC 41 ms 29312 KB
subtask_1_56.txt TLE 2104 ms 27136 KB
subtask_1_57.txt AC 1469 ms 29696 KB
subtask_1_58.txt AC 41 ms 29568 KB
subtask_1_59.txt AC 41 ms 29440 KB
subtask_1_60.txt AC 41 ms 29568 KB
subtask_1_61.txt AC 41 ms 29440 KB
subtask_1_62.txt AC 39 ms 29056 KB
subtask_1_63.txt TLE 2104 ms 27136 KB
subtask_1_64.txt AC 1467 ms 29696 KB