oj.uz

Submission #888870

# Submission time Handle Problem Language Result Execution time Memory
888870 2023-12-18T10:05:01 Z ByeWorld Synchronization (JOI13_synchronization) C++14
100 / 100
 104 ms 28968 KB 
#include <bits/stdc++.h>
#define bupol __builtin_popcount
//#define int long long 
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 1e5+20;
const int MAXA = 2e5+10;
const int LOG = 19;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
 
int n, m, q;
int u[MAXN], v[MAXN];
vector <int> adj[MAXN];
int par[MAXN], sub[MAXN], dep[MAXN], idx[MAXN];
int root[MAXN];
vector <int> ch[MAXN]; //isi chain
bool ty[MAXA];

struct node {
    vector<int> bit;
    int siz;
    //build
    void bd(int x){
        siz = 2*x;
        bit.resize(2*x+5, 0);
    }

    // que
    int que(int x){ // mulai dari idx dep[x], cari ke atas yg duluan 1
        int dp = dep[x]-dep[root[x]]+1;
        int te = 0; // value suffix
        for(int i=dp; i>=1; i-=i&(-i)) te += bit[i];
        //cout << te << ' ' << x << " te\n";
        if(te==0) return -1; // gk ketemu
        //cout << " pp\n";
        // skrg cari te-1
        int ret = 0, sum = 0;
        for(int i=LOG-1; i>=0; i--){
            if(ret + (1<<i) <= siz && sum+bit[ret+(1<<i)] <= te-1){
                sum += bit[ret+(1<<i)];
                ret += (1<<i);
            }
        }

        // ret+1 --> depth dr yg valnya 1
        //cout << ids << " ids\n";
        return ch[root[x]][ret]; // idx yg valuenya 1
    }
    // upd
    void upd(int x, int y){ // depth dr idx = x
        x = dep[x]-dep[root[x]]+1;
        for(int i=x; i<=siz; i+=i&(-i)) bit[i] += y;
    }
} *st[MAXN];

int query(int x){ // x --> idx nya
    while(st[x]->que(x) == -1){
        x = par[root[x]];
    }
    // udh ketemu
    return st[x]->que(x); // idxnya
}
void update(int x, int nw){ // idx x += nw
    st[x]->upd(x, nw);
}

void dfs(int nw, int pa){
    par[nw] = pa; sub[nw] = 1; dep[nw] = dep[pa]+1;
    for(auto nx : adj[nw]){
        if(nx == pa) continue;
        dfs(nx, nw);
        sub[nw] += sub[nx];
    }
}
void build(int x, int y){
    st[x] = new node();
    st[x]->bd(dep[y]-dep[x]+1);
    for(int i=dep[x]+1; i<=dep[y]; i++) st[idx[i]] = st[x];
}
int val[MAXN], up[MAXN];

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    for(int i=1; i<=n-1; i++){
        cin >> u[i] >> v[i];
        adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]);
    }
    dfs(1, 0);
    for(int i=1; i<=n-1; i++){
        if(dep[u[i]] > dep[v[i]]) swap(u[i], v[i]);
    }

    vector <int> qu; qu.pb(1); sub[n+1] = -1; 
    while(!qu.empty()){
        int nw = qu.back(); int tp = nw; qu.pop_back();
        while(true){
            ch[tp].pb(nw);
            root[nw] = tp;
            idx[dep[nw]] = nw;
            
            int big = n+1;
            for(auto nx : adj[nw]){
                if(nx==par[nw]) continue;
                if(sub[nx] > sub[big]) big = nx;
            }
            if(big==n+1) break;
            for(auto nx : adj[nw]){
                if(nx==par[nw] || nx==big) continue;
                qu.pb(nx);
            }
            
            nw = big;
        }
        build(tp, nw);
    }

    for(int i=1; i<=n; i++){
        update(i, 1); 
        val[i] = 1; up[i] = 0;
    }

    for(int i=1; i<=m; i++){
        int x; cin >> x;
        //cout << u[x] << ' ' << v[x] << " atas\n";
        ty[x] ^= 1;
        if(ty[x]){ // ke nyala, join
            update(v[x], -1); //yg bawah
            int idx = query(u[x]);
            val[idx] = val[idx]+val[v[x]]-up[v[x]];
        } else { // ke mati
            int idx = query(v[x]);
            //cout << i << ' ' << x << ' ' << idx << " idx\n";
            update(v[x], 1);
            val[v[x]] = val[idx];
            up[v[x]] = val[idx];
        }
        // for(int j=1; j<=n; j++){
        //     cout << j << ' '<< val[j] << ' ' << up[j] << " up\n";
        // }
    }

    while(q--){
        int x; cin >> x;
        int anc = query(x);
        cout << val[anc] << '\n';
        //cout << anc << ' ' << " anc\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 8 ms 9820 KB Output is correct
8 Correct 7 ms 9820 KB Output is correct
9 Correct 7 ms 9816 KB Output is correct
10 Correct 87 ms 21588 KB Output is correct
11 Correct 88 ms 21588 KB Output is correct
12 Correct 72 ms 24008 KB Output is correct
13 Correct 65 ms 27980 KB Output is correct
14 Correct 65 ms 21048 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 23888 KB Output is correct
2 Correct 59 ms 23764 KB Output is correct
3 Correct 45 ms 21704 KB Output is correct
4 Correct 44 ms 21708 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 9 ms 10116 KB Output is correct
8 Correct 89 ms 21960 KB Output is correct
9 Correct 89 ms 21960 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 22108 KB Output is correct
2 Correct 64 ms 22424 KB Output is correct
3 Correct 65 ms 22460 KB Output is correct
4 Correct 66 ms 22480 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 10 ms 10084 KB Output is correct
7 Correct 104 ms 22452 KB Output is correct
8 Correct 94 ms 24776 KB Output is correct
9 Correct 83 ms 28968 KB Output is correct
10 Correct 97 ms 22336 KB Output is correct
11 Correct 80 ms 26956 KB Output is correct
12 Correct 86 ms 27048 KB Output is correct
13 Correct 66 ms 24776 KB Output is correct