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 |
|
|
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 |