oj.uz

Submission #888840

# Submission time Handle Problem Language Result Execution time Memory
888840 2023-12-18T08:59:12 Z ByeWorld Synchronization (JOI13_synchronization) C++14
30 / 100
 119 ms 262144 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
int ty[MAXA];

struct node {
    int bit[2*MAXN];

    // que
    int que(int x){ // mulai dari idx dep[x], cari ke atas yg duluan 1
        int dp = dep[x];
        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) <= 2*MAXN-10 && sum+bit[ret+(1<<i)] <= te-1){
                sum += bit[ret+(1<<i)];
                ret += (1<<i);
            }
        }

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

int query(int x){ // x --> idx nya
    while(st[x]->que(x) == -1){
        if(x==0) assert(false);

        x = par[root[x]];
    }
    // udh ketemu
    return st[x]->que(x); // idxnya
}
void update(int x, int nw){ // idx x += nw
    st[x]->upd(dep[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();
    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]);
    }

    queue<int> qu; qu.push(1);
    while(!qu.empty()){
        int nw = qu.front(); int tp = nw; qu.pop();
        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.push(nx);
            }
            
            nw = big;
        }
        build(tp, nw);
        if((int)qu.size() > n) assert(false);
    }

    int ins = 0;
    for(int i=1; i<=n; i++) ins += ch[i].size();
    if(ins > n) assert(false);

    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-ty[x];
        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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10072 KB Output is correct
2 Correct 3 ms 13400 KB Output is correct
3 Correct 2 ms 10076 KB Output is correct
4 Correct 5 ms 16220 KB Output is correct
5 Correct 16 ms 50112 KB Output is correct
6 Runtime error 95 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 119 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10076 KB Output is correct
2 Correct 2 ms 10076 KB Output is correct
3 Correct 2 ms 9860 KB Output is correct
4 Correct 2 ms 10076 KB Output is correct
5 Correct 2 ms 10076 KB Output is correct
6 Correct 3 ms 10020 KB Output is correct
7 Correct 10 ms 11356 KB Output is correct
8 Correct 91 ms 22512 KB Output is correct
9 Correct 92 ms 22600 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 22476 KB Output is correct
2 Correct 70 ms 22916 KB Output is correct
3 Correct 65 ms 22984 KB Output is correct
4 Correct 64 ms 22960 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11612 KB Output is correct
2 Correct 3 ms 13144 KB Output is correct
3 Correct 4 ms 13916 KB Output is correct
4 Correct 16 ms 45404 KB Output is correct
5 Runtime error 97 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -