oj.uz

Submission #888857

# Submission time Handle Problem Language Result Execution time Memory
888857 2023-12-18T09:42:10 Z ByeWorld Synchronization (JOI13_synchronization) C++14
50 / 100
 88 ms 24916 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 = x;
        bit.resize(x+5);
    }

    // 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
        int ids = ret; // 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
        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){
        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();
    st[x]->bd(y-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);
    }

    int ins = 0;
    for(int i=1; i<=n; i++) ins += ch[i].size();
    if(ins != n){
        cout << "-1\n"; exit(0);
        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;
        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 8536 KB Output is correct
2 Incorrect 1 ms 8540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 24916 KB Output is correct
2 Correct 59 ms 24900 KB Output is correct
3 Correct 45 ms 23020 KB Output is correct
4 Correct 44 ms 23236 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 2 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 3 ms 8796 KB Output is correct
7 Correct 8 ms 9820 KB Output is correct
8 Correct 88 ms 21684 KB Output is correct
9 Correct 88 ms 21504 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 21508 KB Output is correct
2 Correct 62 ms 21964 KB Output is correct
3 Correct 62 ms 22004 KB Output is correct
4 Correct 62 ms 22048 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Runtime error 8 ms 17244 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -