提出 #19310138


ソースコード 拡げる

Copy
//const int N = 1e5+5;
//int depth[N];
//vi adj[N];
//void dfs(int u, int p){
//    for(int v : adj[u])
//        if(v != p){
//            depth[v] = depth[u]+1;
//            dfs(v,u);
//        }
//}
//void __(){
//    _(int,n);
//    _(vpii,edges,n-1);
//    if(n == 2){
//        print 1,2;
//        return;
//    }
//    vi deg(n+1);
//    for(auto _ : edges)
//        ++deg[_.X],++deg[_.Y];
//    vpii nle;
//    for(auto _ : edges){
//        int u,v;
//        tie(u,v) = _;
//        if(deg[u] > 1 && deg[v] > 1)
//            nle.pb({u,v});
//        adj[u].pb(v);
//        adj[v].pb(u);
//
//    }
//    map<int,int> cnt;
//    for(auto _ : nle){
//        cnt[_.X]++;
//        cnt[_.Y]++;
//    }
//    vi ends;
//    for(auto _ : cnt)
//        if(_.Y == 1)
//            ends.pb(_.X);
//    if(sz(ends) > 2){
//        print -1;
//        return;
//    }
//    int root = 1;
//    while(deg[root] == 1)
//        ++root;
//    if(!ends.empty())
//        root = ends[0];
//    dfs(root,-1);
//    vpii sorted;
//    rep(i,1,n)
//        if(deg[i] > 1)
//            sorted.pb({depth[i],i});
//    sort(all(sorted));
//    vi arr;
//    for(auto _ : sorted){
//        int u = _.Y;
//        int cur = 0;
//        for(int v : adj[u])
//            if(deg[v] == 1)
//                ++cur;
//        arr.pb(cur);
//    }
//    assert(arr[0] > 0);
//    arr.insert(arr.begin(),0);
//    arr[1]--;
//    assert(arr.back() > 0);
//    arr.back()--;
//    arr.pb(0);
//    {
//        vi test = arr;
//        reverse(all(test));
//        if(test < arr)
//            arr = test;
//    }
//    vi ans;
//    int nxt = 1;
//    for(int x : arr){
//        rep(i,x)
//            ans.pb(nxt+1+i);
//        ans.pb(nxt);
//        nxt += x+1;
//    }
//    print ans;
//}
//
#include <map>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <vector>
#include <utility>
#include <iostream>
#include <string>
#define pb push_back
#define REP_INT(i,l,r) for(int i = (l); i <= (r); ++i)
#define REP_ZERO_INT(i,r) for(int i = 0; i < (r); ++i)
#define GET_REP_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define rep(...) GET_REP_MACRO(__VA_ARGS__,REP_ANY,REP_INT,REP_ZERO_INT)(__VA_ARGS__)
#define all(v) (v).begin(), (v).end()
#define sz(v) ll(v.size())
#define X first
#define Y second
#define T1 template<typename T> static
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

T1 ostream& operator<<(ostream& stream, const vector<T>& t);
template <typename F, typename S> static
istream& operator>>(istream& stream, pair<F, S>& t){
    return stream >> t.first >> t.second;
}
T1 istream& read(T, T, istream& = cin);
T1 istream& operator>>(istream& stream, vector<T>& t){
    return read(all(t), stream);
}
T1 istream& read(T b, T e, istream& stream){
    for(T it = b; it != e; ++it)
        stream >> *it;
    return stream;
}
struct _print {
    string sep,end;
    bool space;
    ostream &stream;
    _print(string _sep=" ",string _end="\n",
            ostream &_stream = cout) 
        : sep(_sep),end(_end),space(false),
            stream(_stream) {}
    ~_print() { stream << end; }

    template <typename T>
        _print &operator , (const T &t) {
            if (space) stream << sep;
            space = true;
            stream << t;
            return *this;
        }
};
#define print _print(),
T1 ostream& operator<<(ostream& stream, const vector<T>& t){
    for(int i = 0; i < sz(t); ++i){
        stream << t[i];
        if(i+1 < sz(t))
            stream << ' ';
    }
    return stream;
}
#define INPUT_WITHOUT_INIT(type,name) type name; cin >> name
#define _IWI(type,name,...) type name(__VA_ARGS__); cin >> name
#define GET_INPUT_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define _(...) GET_INPUT_MACRO(__VA_ARGS__,_IWI,_IWI,_IWI,_IWI,_IWI,_IWI,INPUT_WITHOUT_INIT)(__VA_ARGS__)
const int N = 1e5+5;
int depth[N];
vi adj[N];
void dfs(int u, int p){
    for(int v : adj[u])
        if(v != p){
            depth[v] = depth[u]+1;
            dfs(v,u);
        }
}
void __(){
    _(int,n);
    _(vpii,edges,n-1);
    if(n == 2){
        print 1,2;
        return;
    }
    vi deg(n+1);
    for(auto _ : edges)
        ++deg[_.X],++deg[_.Y];
    vpii nle;
    for(auto _ : edges){
        int u,v;
        tie(u,v) = _;
        if(deg[u] > 1 && deg[v] > 1)
            nle.pb({u,v});
        adj[u].pb(v);
        adj[v].pb(u);

    }
    map<int,int> cnt;
    for(auto _ : nle){
        cnt[_.X]++;
        cnt[_.Y]++;
    }
    vi ends;
    for(auto _ : cnt)
        if(_.Y == 1)
            ends.pb(_.X);
    if(sz(ends) > 2){
        print -1;
        return;
    }
    int root = 1;
    while(deg[root] == 1)
        ++root;
    if(!ends.empty())
        root = ends[0];
    dfs(root,-1);
    vpii sorted;
    rep(i,1,n)
        if(deg[i] > 1)
            sorted.pb({depth[i],i});
    sort(all(sorted));
    vi arr;
    for(auto _ : sorted){
        int u = _.Y;
        int cur = 0;
        for(int v : adj[u])
            if(deg[v] == 1)
                ++cur;
        arr.pb(cur);
    }
    assert(arr[0] > 0);
    arr.insert(arr.begin(),0);
    arr[1]--;
    assert(arr.back() > 0);
    arr.back()--;
    arr.pb(0);
    {
        vi test = arr;
        reverse(all(test));
        if(test < arr)
            arr = test;
    }
    vi ans;
    int nxt = 1;
    for(int x : arr){
        rep(i,x)
            ans.pb(nxt+1+i);
        ans.pb(nxt);
        nxt += x+1;
    }
    print ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
        __();
}

提出情報

提出日時
問題 F - Permutation Tree
ユーザ Andres_Unt
言語 C++ (GCC 9.2.1)
得点 900
コード長 5881 Byte
結果 AC
実行時間 128 ms
メモリ 24032 KB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 900 / 900
結果
AC × 3
AC × 55
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
id.txt AC 128 ms 24032 KB
oshii_0.txt AC 64 ms 12788 KB
oshii_1.txt AC 64 ms 12752 KB
rnd10000_9876.txt AC 18 ms 7652 KB
rnd10_4.txt AC 5 ms 5928 KB
rnd10_l.txt AC 6 ms 5936 KB
rnd20000_9876.txt AC 24 ms 8248 KB
rnd20_18.txt AC 5 ms 5972 KB
rnd20_4.txt AC 7 ms 5932 KB
rnd20_l.txt AC 5 ms 5976 KB
rnd3000_2984.txt AC 11 ms 6440 KB
rnd3000_l.txt AC 14 ms 6196 KB
rnd_0.txt AC 53 ms 12188 KB
rnd_1.txt AC 56 ms 11440 KB
rnd_10.txt AC 5 ms 5924 KB
rnd_100.txt AC 5 ms 5984 KB
rnd_1000.txt AC 5 ms 5880 KB
rnd_10000.txt AC 11 ms 6628 KB
rnd_100000.txt AC 45 ms 11464 KB
rnd_1000000.txt AC 76 ms 16080 KB
rnd_1000001.txt AC 83 ms 17724 KB
rnd_1000002.txt AC 125 ms 21992 KB
rnd_100001.txt AC 15 ms 7180 KB
rnd_100002.txt AC 13 ms 6988 KB
rnd_10001.txt AC 11 ms 6084 KB
rnd_10002.txt AC 8 ms 6100 KB
rnd_1001.txt AC 7 ms 5864 KB
rnd_1002.txt AC 8 ms 5940 KB
rnd_101.txt AC 5 ms 5972 KB
rnd_102.txt AC 4 ms 5976 KB
rnd_2.txt AC 67 ms 12756 KB
rnd_3.txt AC 56 ms 12356 KB
rnd_4.txt AC 58 ms 12064 KB
rnd_5.txt AC 56 ms 11808 KB
rnd_6.txt AC 53 ms 11216 KB
rnd_7.txt AC 53 ms 11604 KB
rnd_70.txt AC 5 ms 5968 KB
rnd_700.txt AC 4 ms 5920 KB
rnd_7000.txt AC 9 ms 6308 KB
rnd_70000.txt AC 37 ms 9768 KB
rnd_700000.txt AC 70 ms 15512 KB
rnd_700001.txt AC 49 ms 12260 KB
rnd_700002.txt AC 85 ms 17780 KB
rnd_70001.txt AC 9 ms 6572 KB
rnd_70002.txt AC 11 ms 6924 KB
rnd_7001.txt AC 5 ms 5956 KB
rnd_7002.txt AC 12 ms 6076 KB
rnd_701.txt AC 6 ms 5936 KB
rnd_702.txt AC 5 ms 5980 KB
rnd_71.txt AC 4 ms 5956 KB
rnd_72.txt AC 7 ms 5980 KB
sample1.txt AC 6 ms 5868 KB
sampleId.txt AC 5 ms 5808 KB
sampleNo.txt AC 4 ms 5924 KB
star.txt AC 39 ms 11140 KB