Submission #9698036


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
#define MAXN 100100

int A[MAXN];
int gone[MAXN];
vi V[MAXN];
vi V2[MAXN];
int N,a,b;
vpi E;
vi res,res2;
deque<int> l;

void dfs(int x, int p){
	// cout<<"Safe "<<x<<'\n';
	l.pb(A[x]);
	for (auto v:V[x])if(v!=p && !gone[v]){
		dfs(v,x);
	}
}

int main(){
	cin>>N;
	if (N == 2){
		cout<<"1 2";
		return 0;
	}
	for (int i=1;i<N;++i){
		cin>>a>>b;
		E.pb(a,b);
		V[a].pb(b);V[b].pb(a);
	}
	for (int i=1;i<=N;++i)if(SZ(V[i]) == 1)gone[i] = 1;
	for (auto i : E){
		if (gone[i.f]){
			++A[i.s];
		}else if(gone[i.s]){
			++A[i.f];
		}
	}
	// for (int i=1;i<=N;++i)cout<<gone[i]<<' ';cout<<'\n';
	for (auto i : E){
		// cout<<i.f<<' '<<i.s<<' '<<gone[i.f]<<' '<<gone[i.s]<<'\n';
		if (gone[i.s] || gone[i.f])continue;
		V2[i.f].pb(i.s);
		V2[i.s].pb(i.f);
		// cout<<i.f<<' '<<i.s<<'\n';
	}
	for (int i=1;i<=N;++i)if(SZ(V2[i]) > 2){
		cout<<-1;
		return 0;
	}
	for (int i=1;i<=N;++i){
		if (SZ(V2[i]) == 1){
			dfs(i,-1);
			break;
		}
	}
	
	l.back()--;l.push_back(0);
	l[0]--;l.push_front(0);

	int t = 1;
	for (auto i:l){
		// cout<<"Do "<<i<<'\n';
		if (i == 0){res.pb(t);++t;continue;}
		if (i == 1){res.pb(t+1);res.pb(t);t+=2;continue;}
		for (int k=t+1;k<=t+i;++k){
			res.pb(k);
		}
		res.pb(t);
		t = t+i+1;
	}

	reverse(ALL(l));

	t = 1;
	for (auto i:l){
		if (i == 0){res2.pb(t);++t;continue;}
		if (i == 1){res2.pb(t+1);res2.pb(t);t+=2;continue;}
		for (int k=t+1;k<=t+i;++k){
			res2.pb(k);
		}
		res2.pb(t);
		t = t+i+1;
	}
	// for (auto i :res2)cout<<i<<' ';cout<<'\n';
	bool btr = 0;
	for (int i=0;i<N;++i){
		if (btr)cout<<res[i]<<' ';
		else if (res[i] == res2[i]){
			cout<<res[i]<<' ';
		}else if (res[i] > res2[i]){
			--i;
			swap(res,res2);
			btr = 1;
		}else{
			--i;
			btr = 1;
		}
	}
}

Submission Info

Submission Time
Task F - Permutation Tree
User dvdg6566
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2167 Byte
Status RE
Exec Time 160 ms
Memory 20976 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 3
AC × 53
RE × 2
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 107 ms 20976 KB
oshii_0.txt AC 86 ms 13424 KB
oshii_1.txt AC 86 ms 13424 KB
rnd10000_9876.txt AC 12 ms 6652 KB
rnd10_4.txt AC 3 ms 4992 KB
rnd10_l.txt AC 3 ms 4992 KB
rnd20000_9876.txt AC 21 ms 7672 KB
rnd20_18.txt AC 3 ms 4992 KB
rnd20_4.txt AC 3 ms 4992 KB
rnd20_l.txt AC 3 ms 4992 KB
rnd3000_2984.txt AC 5 ms 5504 KB
rnd3000_l.txt AC 5 ms 5248 KB
rnd_0.txt AC 75 ms 12016 KB
rnd_1.txt AC 74 ms 11504 KB
rnd_10.txt AC 3 ms 4992 KB
rnd_100.txt AC 3 ms 4992 KB
rnd_1000.txt AC 4 ms 4992 KB
rnd_10000.txt AC 10 ms 5884 KB
rnd_100000.txt AC 81 ms 14064 KB
rnd_1000000.txt AC 99 ms 17392 KB
rnd_1000001.txt AC 103 ms 18288 KB
rnd_1000002.txt AC 107 ms 20848 KB
rnd_100001.txt AC 12 ms 6396 KB
rnd_100002.txt AC 11 ms 6268 KB
rnd_10001.txt AC 4 ms 4992 KB
rnd_10002.txt AC 4 ms 5120 KB
rnd_1001.txt AC 3 ms 4992 KB
rnd_1002.txt AC 3 ms 4992 KB
rnd_101.txt AC 3 ms 4992 KB
rnd_102.txt AC 3 ms 4992 KB
rnd_2.txt AC 84 ms 12784 KB
rnd_3.txt AC 77 ms 12144 KB
rnd_4.txt AC 75 ms 12016 KB
rnd_5.txt AC 74 ms 11888 KB
rnd_6.txt AC 64 ms 10992 KB
rnd_7.txt AC 68 ms 11248 KB
rnd_70.txt AC 3 ms 4992 KB
rnd_700.txt AC 3 ms 4992 KB
rnd_7000.txt AC 8 ms 5632 KB
rnd_70000.txt AC 56 ms 11632 KB
rnd_700000.txt AC 72 ms 15344 KB
rnd_700001.txt AC 65 ms 13424 KB
rnd_700002.txt AC 74 ms 16624 KB
rnd_70001.txt AC 8 ms 5760 KB
rnd_70002.txt AC 9 ms 6016 KB
rnd_7001.txt AC 4 ms 4992 KB
rnd_7002.txt AC 4 ms 4992 KB
rnd_701.txt AC 3 ms 4992 KB
rnd_702.txt AC 3 ms 4992 KB
rnd_71.txt AC 3 ms 4992 KB
rnd_72.txt RE 98 ms 4992 KB
sample1.txt AC 3 ms 4992 KB
sampleId.txt AC 3 ms 4992 KB
sampleNo.txt AC 3 ms 4992 KB
star.txt RE 160 ms 10736 KB