Submission #19309555


Source Code Expand

Copy
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define debug(x) cout << #x << ": " << (x) << endl
#else
#define debug(x)
#endif
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int maxn=1e6+7,inf=0x3f3f3f3f,mod=1e9+7;

int fa[maxn],dep[maxn],n,s[maxn],p1[maxn],p2[maxn],np[maxn],top;
vi g[maxn];;

void dfs(int u,int f)
{
    fa[u]=f;
    dep[u]=dep[f]+1;
    for(auto &v:g[u])
    {
        if(v==f) continue;
        dfs(v,u);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0,u,v;i<n-1;++i)
    {
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    int x=0,y=0;
    for(int i=1;i<=n;++i) if(dep[i]>dep[x]) x=i;
    dfs(x,0);
    for(int i=1;i<=n;++i) if(dep[i]>dep[y]) y=i;
    for(int i=y;i;i=fa[i]) s[i]++;
    for(int i=1;i<=n;++i)
    {
        if(!s[i] && ++s[fa[i]]==1)
        {
            cout<<"-1\n";
            return 0;
        }
    }
    vi a;
    for(int i=y;i;i=fa[i]) a.push_back(s[i]);
    top=0;
    for(auto s:a)
    {
        np[top+1]=top+s;
        for(int j=1;j<s;++j) np[top+1+j]=top+j;
        top+=s;
    }
    for(int i=1;i<=n;++i) p1[np[i]]=i;
    reverse(a.begin(),a.end());
    top=0;
    for(auto s:a)
    {
        np[top+1]=top+s;
        for(int j=1;j<s;++j) np[top+1+j]=top+j;
        top+=s;
    }
    for(int i=1;i<=n;++i) p2[np[i]]=i;

    int id=1;
    while(p1[id]==p2[id] && id<n) id++;
    if(p1[id]<p2[id]) for(int i=1;i<=n;++i) cout<<p1[i]<<' ';
    else for(int i=1;i<=n;++i) cout<<p2[i]<<' ';
    cout<<'\n';
    return 0;
}

Submission Info

Submission Time
Task F - Permutation Tree
User Zztrans
Language C++ (GCC 9.2.1)
Score 900
Code Size 1671 Byte
Status AC
Exec Time 88 ms
Memory 37324 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 55
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 88 ms 37324 KB
oshii_0.txt AC 62 ms 30952 KB
oshii_1.txt AC 63 ms 31060 KB
rnd10000_9876.txt AC 32 ms 28156 KB
rnd10_4.txt AC 20 ms 26924 KB
rnd10_l.txt AC 23 ms 27032 KB
rnd20000_9876.txt AC 37 ms 28668 KB
rnd20_18.txt AC 24 ms 26992 KB
rnd20_4.txt AC 28 ms 27024 KB
rnd20_l.txt AC 20 ms 27044 KB
rnd3000_2984.txt AC 22 ms 27336 KB
rnd3000_l.txt AC 26 ms 27224 KB
rnd_0.txt AC 59 ms 30656 KB
rnd_1.txt AC 54 ms 30452 KB
rnd_10.txt AC 22 ms 27032 KB
rnd_100.txt AC 19 ms 26928 KB
rnd_1000.txt AC 28 ms 27048 KB
rnd_10000.txt AC 33 ms 27520 KB
rnd_100000.txt AC 64 ms 32208 KB
rnd_1000000.txt AC 75 ms 34568 KB
rnd_1000001.txt AC 77 ms 35024 KB
rnd_1000002.txt AC 78 ms 36540 KB
rnd_100001.txt AC 32 ms 27944 KB
rnd_100002.txt AC 31 ms 27808 KB
rnd_10001.txt AC 25 ms 27116 KB
rnd_10002.txt AC 21 ms 27128 KB
rnd_1001.txt AC 22 ms 27040 KB
rnd_1002.txt AC 27 ms 27044 KB
rnd_101.txt AC 24 ms 26992 KB
rnd_102.txt AC 25 ms 26896 KB
rnd_2.txt AC 60 ms 31208 KB
rnd_3.txt AC 62 ms 30856 KB
rnd_4.txt AC 63 ms 30644 KB
rnd_5.txt AC 59 ms 30608 KB
rnd_6.txt AC 54 ms 30116 KB
rnd_7.txt AC 56 ms 30372 KB
rnd_70.txt AC 20 ms 26984 KB
rnd_700.txt AC 26 ms 27080 KB
rnd_7000.txt AC 23 ms 27412 KB
rnd_70000.txt AC 50 ms 30700 KB
rnd_700000.txt AC 61 ms 33100 KB
rnd_700001.txt AC 55 ms 31952 KB
rnd_700002.txt AC 61 ms 33928 KB
rnd_70001.txt AC 30 ms 27484 KB
rnd_70002.txt AC 25 ms 27652 KB
rnd_7001.txt AC 22 ms 27056 KB
rnd_7002.txt AC 32 ms 27048 KB
rnd_701.txt AC 27 ms 27036 KB
rnd_702.txt AC 23 ms 26984 KB
rnd_71.txt AC 24 ms 26980 KB
rnd_72.txt AC 25 ms 27016 KB
sample1.txt AC 25 ms 27036 KB
sampleId.txt AC 23 ms 27028 KB
sampleNo.txt AC 21 ms 27036 KB
star.txt AC 60 ms 32084 KB