Submission #19309608


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 1674 Byte
Status AC
Exec Time 83 ms
Memory 37372 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 83 ms 37372 KB
oshii_0.txt AC 60 ms 31036 KB
oshii_1.txt AC 64 ms 31080 KB
rnd10000_9876.txt AC 32 ms 28144 KB
rnd10_4.txt AC 24 ms 27012 KB
rnd10_l.txt AC 21 ms 26892 KB
rnd20000_9876.txt AC 40 ms 28712 KB
rnd20_18.txt AC 21 ms 27024 KB
rnd20_4.txt AC 27 ms 26948 KB
rnd20_l.txt AC 22 ms 27072 KB
rnd3000_2984.txt AC 23 ms 27460 KB
rnd3000_l.txt AC 22 ms 27192 KB
rnd_0.txt AC 55 ms 30868 KB
rnd_1.txt AC 54 ms 30572 KB
rnd_10.txt AC 23 ms 26896 KB
rnd_100.txt AC 28 ms 27068 KB
rnd_1000.txt AC 25 ms 27016 KB
rnd_10000.txt AC 25 ms 27668 KB
rnd_100000.txt AC 61 ms 32252 KB
rnd_1000000.txt AC 72 ms 34492 KB
rnd_1000001.txt AC 76 ms 35144 KB
rnd_1000002.txt AC 81 ms 36624 KB
rnd_100001.txt AC 31 ms 27860 KB
rnd_100002.txt AC 32 ms 27784 KB
rnd_10001.txt AC 22 ms 27032 KB
rnd_10002.txt AC 21 ms 27220 KB
rnd_1001.txt AC 25 ms 27120 KB
rnd_1002.txt AC 22 ms 27120 KB
rnd_101.txt AC 21 ms 27012 KB
rnd_102.txt AC 23 ms 26892 KB
rnd_2.txt AC 62 ms 31112 KB
rnd_3.txt AC 61 ms 30852 KB
rnd_4.txt AC 59 ms 30832 KB
rnd_5.txt AC 58 ms 30672 KB
rnd_6.txt AC 54 ms 30152 KB
rnd_7.txt AC 52 ms 30368 KB
rnd_70.txt AC 21 ms 27076 KB
rnd_700.txt AC 25 ms 27124 KB
rnd_7000.txt AC 30 ms 27440 KB
rnd_70000.txt AC 51 ms 30764 KB
rnd_700000.txt AC 64 ms 33096 KB
rnd_700001.txt AC 56 ms 32032 KB
rnd_700002.txt AC 65 ms 34040 KB
rnd_70001.txt AC 29 ms 27516 KB
rnd_70002.txt AC 30 ms 27764 KB
rnd_7001.txt AC 27 ms 27012 KB
rnd_7002.txt AC 21 ms 27088 KB
rnd_701.txt AC 27 ms 27068 KB
rnd_702.txt AC 26 ms 26948 KB
rnd_71.txt AC 22 ms 27076 KB
rnd_72.txt AC 29 ms 26948 KB
sample1.txt AC 24 ms 27068 KB
sampleId.txt AC 29 ms 27004 KB
sampleNo.txt AC 24 ms 27004 KB
star.txt AC 61 ms 32172 KB