Submission #2355588


Source Code Expand

Copy
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 100005;

int n;
struct edge{
	int x,nxt;
}e[N*2];
int h[N],tot;
int d[N];

void inse(int x,int y){e[++tot].x=y;e[tot].nxt=h[x];h[x]=tot;}

int dis[N],lst[N];
bool vis[N];
int key[N];

void getdis(int x){
	vis[x]=1;
	for(int p=h[x];p;p=e[p].nxt)
	if (!vis[e[p].x]){
		dis[e[p].x]=dis[x]+1;
		lst[e[p].x]=x;
		getdis(e[p].x);
	}
}

int ans1[N],ans2[N];

int main(){
	//freopen("data.in","r",stdin);
	n=get();
	fo(i,2,n){
		int x=get(),y=get();
		inse(x,y),inse(y,x);
		d[x]++,d[y]++;
	}
	getdis(1);
	int val=0,w=1;
	fo(i,2,n)
	if (val<dis[i])w=i,val=dis[i];
	fo(i,1,n)lst[i]=dis[i]=0,vis[i]=0;
	getdis(w);
	val=0;
	int t=w;
	fo(i,1,n)
	if (val<dis[i])t=i,val=dis[i];
	int x=w,y=t;
	int k=0;
	for(int now=y;now;now=lst[now])key[++k]=now;
	fo(i,2,k-1)d[key[i]]-=2;
	d[x]--,d[y]--;
	int pre=1;
	ans1[1]=1;ans1[n]=n;
	fo(i,2,k-1){
		fo(x,pre+2,pre+d[key[i]]+1)ans1[x-1]=x;
		ans1[pre+d[key[i]]+1]=pre+1;
		pre=pre+d[key[i]]+1;
	}
	if (pre!=n-1)return printf("-1\n"),0;
	ans2[1]=1;ans2[n]=n;
	pre=1;
	fd(i,k-1,2){
		fo(x,pre+2,pre+d[key[i]]+1)ans2[x-1]=x;
		ans2[pre+d[key[i]]+1]=pre+1;
		pre=pre+d[key[i]]+1;
	}
	bool pd=1;
	fo(i,1,n)
	if (ans1[i]!=ans2[i]){
		pd=(ans1[i]<ans2[i]);
		break;
	}
	if (pd)fo(i,1,n)printf("%d ",ans1[i]);
	else fo(i,1,n)printf("%d ",ans2[i]);
	return 0;
}

Submission Info

Submission Time
Task F - Permutation Tree
User samjia2000
Language C++14 (GCC 5.4.1)
Score 900
Code Size 1923 Byte
Status AC
Exec Time 44 ms
Memory 8320 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 55
Set Name Test Cases
Sample sample1.txt, sampleId.txt, sampleNo.txt
All id.txt, oshii_0.txt, oshii_1.txt, rnd10000_9876.txt, rnd10_4.txt, rnd10_l.txt, rnd20000_9876.txt, rnd20_18.txt, rnd20_4.txt, rnd20_l.txt, rnd3000_2984.txt, rnd3000_l.txt, rnd_0.txt, rnd_1.txt, rnd_10.txt, rnd_100.txt, rnd_1000.txt, rnd_10000.txt, rnd_100000.txt, rnd_1000000.txt, rnd_1000001.txt, rnd_1000002.txt, rnd_100001.txt, rnd_100002.txt, rnd_10001.txt, rnd_10002.txt, rnd_1001.txt, rnd_1002.txt, rnd_101.txt, rnd_102.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, rnd_5.txt, rnd_6.txt, rnd_7.txt, rnd_70.txt, rnd_700.txt, rnd_7000.txt, rnd_70000.txt, rnd_700000.txt, rnd_700001.txt, rnd_700002.txt, rnd_70001.txt, rnd_70002.txt, rnd_7001.txt, rnd_7002.txt, rnd_701.txt, rnd_702.txt, rnd_71.txt, rnd_72.txt, sample1.txt, sampleId.txt, sampleNo.txt, star.txt
Case Name Status Exec Time Memory
id.txt AC 44 ms 8320 KB
oshii_0.txt AC 25 ms 3456 KB
oshii_1.txt AC 25 ms 3456 KB
rnd10000_9876.txt AC 4 ms 2816 KB
rnd10_4.txt AC 2 ms 2304 KB
rnd10_l.txt AC 2 ms 2304 KB
rnd20000_9876.txt AC 8 ms 3072 KB
rnd20_18.txt AC 2 ms 2304 KB
rnd20_4.txt AC 2 ms 2304 KB
rnd20_l.txt AC 2 ms 2304 KB
rnd3000_2984.txt AC 3 ms 2432 KB
rnd3000_l.txt AC 3 ms 2432 KB
rnd_0.txt AC 23 ms 3200 KB
rnd_1.txt AC 21 ms 3072 KB
rnd_10.txt AC 2 ms 2304 KB
rnd_100.txt AC 2 ms 2304 KB
rnd_1000.txt AC 2 ms 2304 KB
rnd_10000.txt AC 4 ms 2560 KB
rnd_100000.txt AC 26 ms 4864 KB
rnd_1000000.txt AC 38 ms 6144 KB
rnd_1000001.txt AC 39 ms 6528 KB
rnd_1000002.txt AC 42 ms 7808 KB
rnd_100001.txt AC 5 ms 2688 KB
rnd_100002.txt AC 5 ms 2688 KB
rnd_10001.txt AC 2 ms 2304 KB
rnd_10002.txt AC 2 ms 2304 KB
rnd_1001.txt AC 2 ms 2304 KB
rnd_1002.txt AC 2 ms 2304 KB
rnd_101.txt AC 2 ms 2304 KB
rnd_102.txt AC 2 ms 2304 KB
rnd_2.txt AC 25 ms 3456 KB
rnd_3.txt AC 23 ms 3328 KB
rnd_4.txt AC 22 ms 3200 KB
rnd_5.txt AC 22 ms 3200 KB
rnd_6.txt AC 19 ms 2944 KB
rnd_7.txt AC 20 ms 3072 KB
rnd_70.txt AC 2 ms 2304 KB
rnd_700.txt AC 2 ms 2304 KB
rnd_7000.txt AC 3 ms 2432 KB
rnd_70000.txt AC 19 ms 3840 KB
rnd_700000.txt AC 28 ms 5504 KB
rnd_700001.txt AC 25 ms 4480 KB
rnd_700002.txt AC 29 ms 6144 KB
rnd_70001.txt AC 4 ms 2560 KB
rnd_70002.txt AC 4 ms 2560 KB
rnd_7001.txt AC 2 ms 2304 KB
rnd_7002.txt AC 2 ms 2304 KB
rnd_701.txt AC 2 ms 2304 KB
rnd_702.txt AC 2 ms 2304 KB
rnd_71.txt AC 2 ms 2304 KB
rnd_72.txt AC 2 ms 2304 KB
sample1.txt AC 2 ms 2304 KB
sampleId.txt AC 2 ms 2304 KB
sampleNo.txt AC 2 ms 2304 KB
star.txt AC 27 ms 4864 KB