Submission #974409

#TimeUsernameProblemLanguageResultExecution timeMemory
974409vjudge1Village (BOI20_village)C11
100 / 100
40 ms12116 KiB
#include<stdio.h> #define N 100000 #define M (2*N) int ded[N],n, p1[N],head[N], nxt[M], vv[M], eo = 1, tin[N], timer, aux[N],sz[N],qu[N],qh,qt,deg[N]; void link(int u,int v) { int i = eo++; nxt[i]=head[u],vv[i]=v,head[u]=i; ++deg[v]; } long long max, min; void dfs(int u,int p) { sz[u]=1; aux[tin[u] = timer++] = u; for (int j =head[u];j;j=nxt[j])if(p!=vv[j]){ dfs(vv[j],u); max+=sz[vv[j]]<(n-sz[vv[j]])?sz[vv[j]]:n-sz[vv[j]]; sz[u]+=sz[vv[j]]; } } int main() { scanf("%d",&n); for(int i=1,u,v;i<n;++i)scanf("%d%d",&u,&v),link(--u,--v),link(v,u); dfs(0,0); for(int i=0;i<n;++i)p1[i]=i; for(int i=0;i<n;++i)if(deg[i]==1)qu[qh++]=i; while(qh-qt) { int temp,u=qu[qt++],f=0; for(int j=head[u];j;j=nxt[j]) { int v=vv[j]; if(!ded[v]){ if(--deg[v]==1) qu[qh++]=v; f=1; if(p1[u]==u) { min+=2; temp=p1[u],p1[u]=p1[v],p1[v]=temp; } break; } } if(!f&&p1[u]==u) { int v=vv[head[u]]; temp=p1[u],p1[u]=p1[v],p1[v]=temp; min+=2; } ded[u]=1; } printf("%lld %lld\n",min,max<<1); for(int i=0;i<n;++i) printf("%d ",1+p1[i]); putchar(10); for(int i=0;i<n;++i) printf("%d ",1+aux[(tin[i]+n/2)%n]); }

Compilation message (stderr)

Village.c: In function 'main':
Village.c:28:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d",&n);
      |     ^~~~~~~~~~~~~~
Village.c:29:29: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     for(int i=1,u,v;i<n;++i)scanf("%d%d",&u,&v),link(--u,--v),link(v,u);
      |                             ^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...