Submission #9697880
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 (A[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); res.pb(t+i); 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); res2.pb(t+i); t = t+i+1; } 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]){ swap(res,res2); btr = 1; }else{ btr = 1; } } }
Submission Info
Submission Time | |
---|---|
Task | F - Permutation Tree |
User | dvdg6566 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2129 Byte |
Status | WA |
Exec Time | 107 ms |
Memory | 20976 KB |
Judge Result
Set Name | Sample | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 900 | ||||||||
Status |
|
|
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 | 87 ms | 13424 KB |
oshii_1.txt | AC | 86 ms | 13424 KB |
rnd10000_9876.txt | WA | 12 ms | 6524 KB |
rnd10_4.txt | AC | 3 ms | 4992 KB |
rnd10_l.txt | WA | 3 ms | 4992 KB |
rnd20000_9876.txt | WA | 21 ms | 7416 KB |
rnd20_18.txt | WA | 3 ms | 4992 KB |
rnd20_4.txt | WA | 3 ms | 4992 KB |
rnd20_l.txt | WA | 3 ms | 4992 KB |
rnd3000_2984.txt | WA | 6 ms | 5376 KB |
rnd3000_l.txt | WA | 5 ms | 5248 KB |
rnd_0.txt | AC | 76 ms | 12016 KB |
rnd_1.txt | AC | 70 ms | 11504 KB |
rnd_10.txt | WA | 3 ms | 4992 KB |
rnd_100.txt | WA | 3 ms | 4992 KB |
rnd_1000.txt | WA | 4 ms | 4992 KB |
rnd_10000.txt | WA | 10 ms | 5884 KB |
rnd_100000.txt | WA | 82 ms | 14064 KB |
rnd_1000000.txt | WA | 99 ms | 16624 KB |
rnd_1000001.txt | WA | 100 ms | 17648 KB |
rnd_1000002.txt | WA | 106 ms | 19056 KB |
rnd_100001.txt | WA | 12 ms | 6396 KB |
rnd_100002.txt | WA | 11 ms | 6268 KB |
rnd_10001.txt | WA | 4 ms | 4992 KB |
rnd_10002.txt | WA | 4 ms | 5120 KB |
rnd_1001.txt | WA | 3 ms | 4992 KB |
rnd_1002.txt | WA | 3 ms | 4992 KB |
rnd_101.txt | WA | 3 ms | 4992 KB |
rnd_102.txt | WA | 3 ms | 4992 KB |
rnd_2.txt | AC | 85 ms | 12784 KB |
rnd_3.txt | AC | 77 ms | 12144 KB |
rnd_4.txt | AC | 74 ms | 12016 KB |
rnd_5.txt | AC | 74 ms | 11888 KB |
rnd_6.txt | AC | 64 ms | 10992 KB |
rnd_7.txt | AC | 69 ms | 11248 KB |
rnd_70.txt | WA | 3 ms | 4992 KB |
rnd_700.txt | WA | 4 ms | 4992 KB |
rnd_7000.txt | WA | 8 ms | 5632 KB |
rnd_70000.txt | WA | 57 ms | 11632 KB |
rnd_700000.txt | WA | 73 ms | 15216 KB |
rnd_700001.txt | WA | 65 ms | 13168 KB |
rnd_700002.txt | WA | 74 ms | 16112 KB |
rnd_70001.txt | WA | 8 ms | 5760 KB |
rnd_70002.txt | WA | 9 ms | 5888 KB |
rnd_7001.txt | WA | 4 ms | 4992 KB |
rnd_7002.txt | WA | 4 ms | 4992 KB |
rnd_701.txt | WA | 3 ms | 4992 KB |
rnd_702.txt | WA | 3 ms | 4992 KB |
rnd_71.txt | WA | 3 ms | 4992 KB |
rnd_72.txt | WA | 3 ms | 4992 KB |
sample1.txt | WA | 3 ms | 4992 KB |
sampleId.txt | AC | 3 ms | 4992 KB |
sampleNo.txt | AC | 3 ms | 4992 KB |
star.txt | WA | 79 ms | 13936 KB |