Submission #974393

#	Time	Username	Problem	Language	Result	Execution time	Memory
974393		sleepntsheep	Village (BOI20_village)	C11	50 / 100	38 ms	11876 KiB

Village

#include<stdio.h>

#define N 100000
#define M (2*N)

int n, head[N], nxt[M], vv[M], eo = 1, tin[N], timer, aux[N],sz[N];
void link(int u,int v)
{
    int i = eo++;
    nxt[i]=head[u],vv[i]=v,head[u]=i;
}

long long max;
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);
    printf("0 %lld\n",max<<1);
    for(int i=0;i<n;++i)
        printf("%d ",1+aux[(tin[i]+n/2)%n]);
    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:27:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d",&n);
      |     ^~~~~~~~~~~~~~
Village.c:28:29: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     for(int i=1,u,v;i<n;++i)scanf("%d%d",&u,&v),link(--u,--v),link(v,u);
      |                             ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50