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