Submission #1153710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153710		Otalp	Amusement Park (JOI17_amusement_park)	C++20	100 / 100	28 ms	12360 KiB

Joi

#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second

namespace{
    int pos[200100];
    int a[200100], cnt[200100];
    vector<int> dq[200100], q[200100];
    const int MAXK = 60;

    void dfs0(int v){
        pos[v] = 1;
        for(int to: dq[v]){
            if(pos[to]) continue;
            q[v].pb(to);
            q[to].pb(v);
            dfs0(to);
        }    
    }


    // pii dfs1(int v, int p){
    //     pii h={1, v};
    //     for(int to: q[v]){
    //         if(p == to) continue;
    //         pii g=dfs1(to, v);
    //         h = max(h, {g.ff + 1, g.ss});
    //     }
    //     return h;
    // }

    set<pii> h;
    int K = 0;
    int P[200100];

    void dfs1(int v, int p){
        if(K < MAXK){
            a[v] = K ++;
            // if(h.find({a[p], p}) != h.end() and (p != 0 or (p == 0 and cnt[0] > 1))) h.erase(h.find({a[p], p}));
            // h.insert({a[v], v});
            if(p != -1) cnt[v] = 1;
            if(p != -1) cnt[p] ++;
        }
        P[v] = p;
        for(int to: q[v]){
            if(p == to) continue;
            dfs1(to, v);
        }
    }

    void dfs2(int v, int p){
        pii g={-1, -1};
        // cout<<v<<'\n';
        if(a[v] == -1){
            auto it = h.begin();
            if(it -> ss == p){
                it++;
            }
            g = *it;
            h.erase(it);
            a[v] = g.ff;
            cnt[v] = 1;
            cnt[p] ++;
            cnt[g.ss] = 0;
            h.insert({a[v], v});
            if(cnt[p] == 2 and h.find({a[p], p}) != h.end()) h.erase(h.find({a[p], p}));
            cnt[P[g.ss]]--;
            if(cnt[P[g.ss]] == 1) h.insert({a[P[g.ss]], P[g.ss]});
        }
        // cout<<"ok\n";
        int dp = -1;
        for(int to: q[v]){
            if(to == p) continue;
            // dp = P[v];
            P[v] = to;
            dfs2(to, v);
        }
        P[v] = p;
        if(g.ff != -1){
            cnt[v] = 0;
            cnt[p] --;
            cnt[P[g.ss]] ++;
            cnt[g.ss] = 1;
            // for(pii x:h) cout<<x.ff<<' '<<x.ss<<'\n';
            h.erase(h.find({a[v], v}));
            // cout<<"ok";
            // cout<<"suka\n";
            if(cnt[p] == 1) h.insert({a[p], p});
            if(cnt[P[g.ss]] == 2 and h.find({a[P[g.ss]], P[g.ss]}) != h.end()) h.erase(h.find({a[P[g.ss]], P[g.ss]}));
            h.insert(g);
        }
        // cout<<"ok"<<' '<<v<<'\n';
        // cout<<"suka\n";
        
    }
}


void Joi(int n, int m, int A[], int B[], long long X, int T){
    for(int i=0; i<n; i++) a[i] = -1;
    for(int i=0; i<m; i++){
        int l = A[i], r = B[i];
        dq[l].pb(r);
        dq[r].pb(l);
    }
    dfs0(0);
    // int f = (dfs1(0, -1)).ss;
    // pii g = (dfs1(f, -1));
    // int s = g.ss;
    // if(g.ff < 60){
    dfs1(0, -1);
    for(int i=0; i<n; i++){
        // cout<<i<<' '<<cnt[i]<<'\n';
        if(a[i] != -1 and cnt[i] == 1) h.insert({a[i], i});
    }
    dfs2(0, -1);  
    for(int i=0; i<n; i++){
        // cout<<a[i]<<' ';
        MessageBoard(i, bool(X & (1ll << a[i])));
    }  
    // for(int i=0; i<60; i++){
    //     MessageBoard(i, bool(X & (1ll << i)));
    // } 
    // for(int i=60; i<n; i++){
    //     MessageBoard(i, 0);
    // }
}

Ioi

#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second



namespace{
    int pos[200100];
    int a[200100], cnt[200100];
    vector<int> dq[200100], q[200100];
    const int MAXK = 60;

    void dfs0(int v){
        pos[v] = 1;
        for(int to: dq[v]){
            if(pos[to]) continue;
            q[v].pb(to);
            q[to].pb(v);
            dfs0(to);
        }    
    }


    // pii dfs1(int v, int p){
    //     pii h={1, v};
    //     for(int to: q[v]){
    //         if(p == to) continue;
    //         pii g=dfs1(to, v);
    //         h = max(h, {g.ff + 1, g.ss});
    //     }
    //     return h;
    // }

    set<pii> h;
    int K = 0;
    int P[200100];

    void dfs1(int v, int p){
        if(K < MAXK){
            a[v] = K ++;
            // if(h.find({a[p], p}) != h.end() and (p != 0 or (p == 0 and cnt[0] > 1))) h.erase(h.find({a[p], p}));
            // h.insert({a[v], v});
            if(p != -1) cnt[v] = 1;
            if(p != -1) cnt[p] ++;
        }
        P[v] = p;
        for(int to: q[v]){
            if(p == to) continue;
            dfs1(to, v);
        }
    }

    
    void dfs2(int v, int p){
        pii g={-1, -1};
        // cout<<v<<'\n';
        if(a[v] == -1){
            auto it = h.begin();
            if(it -> ss == p){
                it++;
            }
            g = *it;
            h.erase(it);
            a[v] = g.ff;
            cnt[v] = 1;
            cnt[p] ++;
            cnt[g.ss] = 0;
            h.insert({a[v], v});
            if(cnt[p] == 2 and h.find({a[p], p}) != h.end()) h.erase(h.find({a[p], p}));
            cnt[P[g.ss]]--;
            if(cnt[P[g.ss]] == 1) h.insert({a[P[g.ss]], P[g.ss]});
        }
        // cout<<"ok\n";
        int dp = -1;
        for(int to: q[v]){
            if(to == p) continue;
            // dp = P[v];
            P[v] = to;
            dfs2(to, v);
        }
        P[v] = p;
        if(g.ff != -1){
            cnt[v] = 0;
            cnt[p] --;
            cnt[P[g.ss]] ++;
            cnt[g.ss] = 1;
            // for(pii x:h) cout<<x.ff<<' '<<x.ss<<'\n';
            h.erase(h.find({a[v], v}));
            // cout<<"ok";
            // cout<<"suka\n";
            if(cnt[p] == 1) h.insert({a[p], p});
            if(cnt[P[g.ss]] == 2 and h.find({a[P[g.ss]], P[g.ss]}) != h.end()) h.erase(h.find({a[P[g.ss]], P[g.ss]}));
            h.insert(g);
        }
        // cout<<"ok"<<' '<<v<<'\n';
        // cout<<"suka\n";
        
    }
}

ll X;
int us[100];

void dfs4(int v, int p, int k){
    X += (1ll << a[v]) * k;
    us[a[v]] = 1;
    for(int to: q[v]){
        if(p == to) continue;
        if(us[a[to]] == 1) continue;
        dfs4(to, v, Move(to));
        Move(v);
    }
}

long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
    for(int i=0; i<n; i++) a[i] = -1;
    for(int i=0; i<m; i++){
        int l = A[i], r = B[i];
        dq[l].pb(r);
        dq[r].pb(l);
    }
    dfs0(0);
    for(int i=0; i<60; i++) us[i] = 0;
    // int f = (dfs1(0, -1)).ss;
    // pii g = (dfs1(f, -1));
    // int s = g.ss;
    // if(g.ff < 60){
    dfs1(0, -1);
    for(int i=0; i<n; i++){
        if(a[i] != -1 and cnt[i] == 1) h.insert({a[i], i});
    }
    dfs2(0, -1);  
    X = 0;
    dfs4(P, -1, V);
    return X;
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17