oj.uz

Submission #949418

# Submission time Handle Problem Language Result Execution time Memory
949418 2024-03-19T08:26:54 Z browntoad Multidrink (POI13_mul) C++14
100 / 100
 465 ms 102080 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20828 KB Output is correct
2 Correct 5 ms 20740 KB Output is correct
3 Correct 5 ms 20828 KB Output is correct
4 Correct 5 ms 20828 KB Output is correct
5 Correct 7 ms 20924 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20824 KB Output is correct
2 Correct 5 ms 20828 KB Output is correct
3 Correct 5 ms 20828 KB Output is correct
4 Correct 5 ms 20824 KB Output is correct
5 Correct 5 ms 20828 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 20828 KB Output is correct
2 Correct 6 ms 20828 KB Output is correct
3 Correct 6 ms 20828 KB Output is correct
4 Correct 5 ms 20828 KB Output is correct
5 Correct 6 ms 20828 KB Output is correct
6 Correct 5 ms 20700 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20828 KB Output is correct
2 Correct 5 ms 20828 KB Output is correct
3 Correct 5 ms 20824 KB Output is correct
4 Correct 5 ms 20824 KB Output is correct
5 Correct 6 ms 20828 KB Output is correct
6 Correct 5 ms 20828 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 20828 KB Output is correct
2 Correct 5 ms 20828 KB Output is correct
3 Correct 7 ms 20920 KB Output is correct
4 Correct 5 ms 20828 KB Output is correct
5 Correct 5 ms 20916 KB Output is correct
6 Correct 5 ms 20828 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20828 KB Output is correct
2 Correct 5 ms 20828 KB Output is correct
3 Correct 5 ms 20920 KB Output is correct
4 Correct 5 ms 20828 KB Output is correct
5 Correct 6 ms 20828 KB Output is correct
6 Correct 5 ms 20828 KB Output is correct

Subtask #7
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20828 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 20828 KB Output is correct

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20824 KB Output is correct

Subtask #10
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 20824 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20920 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 20828 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 20828 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21340 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 21084 KB Output is correct
2 Correct 5 ms 20828 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 32388 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 32752 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 30100 KB Output is correct
2 Correct 5 ms 20828 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 62168 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 64436 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 65828 KB Output is correct
2 Correct 378 ms 68776 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 102080 KB Output is correct
2 Correct 391 ms 99648 KB Output is correct