Submission #9697394


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;
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 (A[i] >= 1){
			dfs(i,-1);
			break;
		}
	}
	// if (SZ(l) == 0)assert(0);
	assert(SZ(l) == 1);
	sort(ALL(l));

	if (l[0] > 2){
		l.push_front(l.back());
		l.pop_back();
	}
	int t = 1;
	for (auto i:l){
		// cout<<"Do "<<i<<'\n';
		if (i == 0){
			res.pb(t);
			++t;
			continue;
		}
		if (SZ(res) == 0){
			res.pb(1);
			for (int j=3;j<t+i;++j)res.pb(j);
			if (i >= 1)res.pb(2);
			if (i >= 2)res.pb(i+t);
			t = t+i+1;
			continue;
		}
		for (int k=t+1;k<t+i;++k){
			res.pb(k);
		}
		res.pb(t);
		res.pb(t+i);
		t = t+i+1;
	}

	assert(SZ(res) == N);
	for (auto i:res){cout<<i<<' ';assert(i<=N);}
}

Submission Info

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

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 1
RE × 2
AC × 13
RE × 42
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 RE 193 ms 17904 KB
oshii_0.txt AC 90 ms 13424 KB
oshii_1.txt AC 100 ms 13424 KB
rnd10000_9876.txt RE 108 ms 6140 KB
rnd10_4.txt RE 100 ms 4992 KB
rnd10_l.txt RE 101 ms 4992 KB
rnd20000_9876.txt RE 114 ms 6776 KB
rnd20_18.txt RE 99 ms 4992 KB
rnd20_4.txt RE 99 ms 4992 KB
rnd20_l.txt RE 99 ms 4992 KB
rnd3000_2984.txt RE 101 ms 5376 KB
rnd3000_l.txt RE 103 ms 5120 KB
rnd_0.txt AC 77 ms 12016 KB
rnd_1.txt AC 71 ms 11504 KB
rnd_10.txt RE 99 ms 4992 KB
rnd_100.txt RE 101 ms 4992 KB
rnd_1000.txt RE 101 ms 4992 KB
rnd_10000.txt RE 103 ms 5628 KB
rnd_100000.txt RE 168 ms 10864 KB
rnd_1000000.txt RE 184 ms 13424 KB
rnd_1000001.txt RE 181 ms 14448 KB
rnd_1000002.txt RE 188 ms 15856 KB
rnd_100001.txt RE 106 ms 5884 KB
rnd_100002.txt RE 108 ms 5884 KB
rnd_10001.txt RE 100 ms 4992 KB
rnd_10002.txt RE 102 ms 4992 KB
rnd_1001.txt RE 101 ms 4992 KB
rnd_1002.txt RE 99 ms 4992 KB
rnd_101.txt RE 100 ms 4992 KB
rnd_102.txt RE 100 ms 4992 KB
rnd_2.txt AC 94 ms 12784 KB
rnd_3.txt AC 82 ms 12144 KB
rnd_4.txt AC 86 ms 12016 KB
rnd_5.txt AC 85 ms 11888 KB
rnd_6.txt AC 71 ms 10992 KB
rnd_7.txt AC 79 ms 11248 KB
rnd_70.txt RE 103 ms 4992 KB
rnd_700.txt RE 105 ms 4992 KB
rnd_7000.txt RE 106 ms 5376 KB
rnd_70000.txt RE 146 ms 9588 KB
rnd_700000.txt RE 158 ms 12784 KB
rnd_700001.txt RE 157 ms 10608 KB
rnd_700002.txt RE 161 ms 13680 KB
rnd_70001.txt RE 112 ms 5504 KB
rnd_70002.txt RE 103 ms 5632 KB
rnd_7001.txt RE 101 ms 4992 KB
rnd_7002.txt RE 100 ms 4992 KB
rnd_701.txt RE 105 ms 4992 KB
rnd_702.txt RE 102 ms 4992 KB
rnd_71.txt RE 99 ms 4992 KB
rnd_72.txt AC 3 ms 4992 KB
sample1.txt RE 100 ms 4992 KB
sampleId.txt RE 103 ms 4992 KB
sampleNo.txt AC 3 ms 4992 KB
star.txt AC 82 ms 13296 KB