Submission #949418

#	Time	Username	Problem	Language	Result	Execution time	Memory
949418		browntoad	Multidrink (POI13_mul)	C++14	100 / 100	465 ms	102080 KiB

mul

#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define RREP1(i, n) for(int i = (n); i >= 1; i--)
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define ppi pair<pii, int>
#define pip pair<int, pii>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define endl '\n'
#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)


const ll maxn = 5e5+5;
const ll maxm = 1e4+5;
const ll mod = 1e9+7;
const ll inf = 1ll<<60;

vector<int> ans;
int n;
vector<pii> inp(maxn);
vector<pii> g[maxn];

vector<bool> ban(maxn);

vector<int> sz(maxn);

vector<int> path;
bool dfs(int x, int prev){
    if (x == n){
        path.pb(x);
        return 1;
    }
    for (auto y:g[x]){
        if (y.f != prev && dfs(y.f, x)){
            path.pb(x);
            ban[y.s] = 1;
            return 1;
        }
    }
    return 0;
}

bool dp[maxn][3];
pii trans[maxn][3]; // transition
void dfs2(int x, int prev){
    vector<pii> ou;
    sz[x] = 1;
    for (auto y:g[x]){
        if (!ban[y.s] && y.f != prev){
            dfs2(y.f, x);
            ou.pb({sz[y.f], y.f});
            sz[x] += sz[y.f];
        }
    }
    if (sz[x] == 1){
        REP(z, 3) dp[x][z] = 1;
        return;
    }
    sort(ALL(ou), greater<pii> ());
    // a
    dp[x][0] = (dp[ou[0].s][1] && (SZ(ou) <= 1 || ou[1].f <= 1));
    if (dp[x][0]) trans[x][0].f = ou[0].s;
    // b
    dp[x][1] = (dp[ou[0].s][0] && (SZ(ou) <= 1 || ou[1].f <= 1));
    if (dp[x][1]) trans[x][1].f = ou[0].s;
    // c
    if (SZ(ou) >= 2){
        dp[x][2] = (((dp[ou[0].s][0] && dp[ou[1].s][1]) || (dp[ou[1].s][0] && dp[ou[0].s][1])) && (SZ(ou) <= 2 || ou[2].f <= 1));
        if (dp[ou[0].s][0] && dp[ou[1].s][1]) trans[x][2] = {ou[0].s, ou[1].s};
        else trans[x][2] = {ou[1].s, ou[0].s};
    }
}
void run(int x, int typ, int prev){
    vector<int> rem;
    for (auto y:g[x]){
        if (!ban[y.s] && y.f != prev && y.f != trans[x][typ].f && y.f != trans[x][typ].s) rem.pb(y.f);
    }
    if (sz[x] == 1){
        ans.pb(x);
        return;
    }
    if (typ == 0){
        ans.pb(x);
        run(trans[x][0].f, 1, x);
        for (auto v:rem) ans.pb(v);
    }
    else if (typ == 1){
        for (auto v:rem) ans.pb(v);
        run(trans[x][1].f, 0, x);
        ans.pb(x);
    }
    else{
        for (auto v:rem) ans.pb(v);
        run(trans[x][2].f, 0, x);
        ans.pb(x);
        run(trans[x][2].s, 1, x);
    }
}

void init(){
    cin>>n;
    REP(i, n-1){
        int u, v; cin>>u>>v;
        g[u].pb({v, i});
        g[v].pb({u, i});
        inp[i] = {u, v};
    }
}


signed main(){
    IOS();
    init();
    dfs(1, -1);
    reverse(ALL(path));

    int prev = 1; // b
    bool gg = false;
    for (auto u:path) {
        dfs2(u, -1);
        if (sz[u] == 1){
            ans.pb(u);
            prev = 1;
            continue;
        }
        // special cases
        if (u == 1){
            if (!dp[u][0]){
                gg = 1;
                break;
            }
            run(u, 0, -1);
            prev = 0;
            continue;
        }
        if (u == n){
            if (!dp[u][1] || prev != 1){
                gg = 1;
                break;
            }
            run(u, 1, -1);
            prev = 1;
            continue;
        }

        if (dp[u][1] && prev == 1){
            run(u, 1, -1);
            prev = 1;
        }
        else if (dp[u][2] && prev == 1){
            run(u, 2, -1);
            prev = 2;
        }
        else if (dp[u][0]){
            run(u, 0, -1);
            prev = 0;
        }
        else {
            gg = 1;
            break;
        }
    }
    if (gg) cout<<"BRAK"<<endl;
    else{
        for (auto a:ans) cout<<a<<endl;
    }

}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5