oj.uz

Submission #888835

# Submission time Handle Problem Language Result Execution time Memory
888835 2023-12-18T08:50:32 Z ByeWorld Synchronization (JOI13_synchronization) C++14
30 / 100
 307 ms 262144 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#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 = 4e5+20;
const int LOG = 21;
const int MOD = 998244353;
const int SQRT = 520;
const int INF = 1e18;
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[MAXN];

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 + (1ll<<i) <= 2*MAXN-10 && sum+bit[ret+(1ll<<i)] <= te-1){
                sum += bit[ret+(1ll<<i)];
                ret += (1ll<<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){
            cout << "-1\n"; exit(0);
        }
        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);
    }

    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 9 ms 39512 KB Output is correct
2 Correct 16 ms 64604 KB Output is correct
3 Correct 8 ms 39516 KB Output is correct
4 Correct 20 ms 89688 KB Output is correct
5 Runtime error 66 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 100 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 8 ms 39516 KB Output is correct
2 Correct 7 ms 39516 KB Output is correct
3 Correct 8 ms 39516 KB Output is correct
4 Correct 7 ms 39516 KB Output is correct
5 Correct 7 ms 39516 KB Output is correct
6 Correct 9 ms 39516 KB Output is correct
7 Correct 33 ms 42668 KB Output is correct
8 Correct 284 ms 59092 KB Output is correct
9 Correct 278 ms 58464 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 59000 KB Output is correct
2 Correct 236 ms 58816 KB Output is correct
3 Correct 249 ms 59256 KB Output is correct
4 Correct 246 ms 58928 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 52312 KB Output is correct
2 Correct 12 ms 64604 KB Output is correct
3 Correct 16 ms 71000 KB Output is correct
4 Runtime error 54 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -