Submission #807038

#	Time	Username	Problem	Language	Result	Execution time	Memory
807038		Hakiers	Synchronization (JOI13_synchronization)	C++17	100 / 100	570 ms	25728 KiB

synchronization

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 7;
const int BASE = 1 << 18;
const int LOG = 17;
vector<pair<int, int>> G[MAXN];
int TREE[BASE << 1];
int jmp[MAXN][LOG  + 1];
int a[MAXN], b[MAXN];
int depth[MAXN];
int pre[MAXN], post[MAXN];
int wsk[MAXN];
bool active[MAXN];
int tajm;
int n, m, q;

void dfs(int v, int p, int d = 0){

    pre[v] = ++tajm;
    jmp[v][0] = p;
    depth[v] = d;

    for(int k = 1; k <= LOG; k++)
        jmp[v][k] = jmp[jmp[v][k-1]][k-1];
    
    for(auto [u, id] : G[v]){
        if(u == p) continue;
        wsk[id] = u;
        dfs(u, v, d+1);
    }

    post[v] = ++tajm;
}

void update(int v, int val){

    v += BASE;
    TREE[v] = val;

    v/=2;

    while(v > 0){
        int l = 2*v, r = 2*v + 1;
        TREE[v] = TREE[l] + TREE[r];

        v/=2;
    }
}

int query(int a, int b){

    a += BASE - 1;
    b += BASE + 1;
    int res = 0;

    while(a/2 != b/2){
        if(a % 2 == 0) res += TREE[a+1];
        if(b % 2 == 1) res += TREE[b-1];

        a/=2; b/=2;
    }

    return res;
}

int find(int u){

    int v = u;

    for(int k = LOG; k >= 0; k--){
        if(query(pre[jmp[v][k]] + 1, pre[u]) >= (depth[u] - depth[jmp[v][k]]))
            v = jmp[v][k];
    }

    if(query(pre[v], pre[u]) == (depth[u] - depth[v]))
        return v;
    
    return u;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;

    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        G[a].push_back({b, i});
        G[b].push_back({a, i});
    }

    dfs(1, 1);
    for(int i = 1; i <= n; i++) a[i] = 1;

    for(int i = 1; i <= m; i++){
        int x;

        cin >> x;

        if(!active[x]){
            int u = wsk[x];
            update(pre[u], 1);
            update(post[u], -1);
            int v = find(u);
            a[v] = a[v] + a[u] - b[u];
        }
        else{
            int u = wsk[x];
            a[u] = b[u] = a[find(u)];
            update(pre[u], 0);
            update(post[u], 0);

        }
        active[x] ^=1;
    }

    for(int i = 1; i <= q; i++){
        int x;
        cin >> x;
        cout << a[find(x)] << endl;
    }

}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40