Submission #1248529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248529		piedav	Synchronization (JOI13_synchronization)	C++20	100 / 100	309 ms	37048 KiB

synchronization

#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;

vector<vector<int> > adj;
vector<vector<int> > anc;
vector<int> d;
vector<int> bit;
vector<int> tin;
vector<int> tout;
int timer = 0;

void add(int pos, int x) {
    for(int i = pos; i < bit.size(); i += (i&(-1*i))) {
        bit[i] += x;
    }
}

void addRange(int l, int r, int x) {
    add(l, x);
    add(r+1, -x);
}

int getVal(int pos) {
    if(pos == 0) return -1;
    pos = tin[pos];
    int ans = 0;
    for(int i = pos; i > 0; i -= ((i&(-1*i)))) {
        ans += bit[i];
    }
    return ans;
}

const int ln = 20;

void dfs(int u, int p) {
    tin[u] = ++timer;
    anc[u][0] = p; for(int i = 1; i < ln; ++i) {anc[u][i] = anc[anc[u][i-1]][i-1];}
    d[u] = d[p] + 1;
    for(int v : adj[u]) {
        if(v==p) continue;
        dfs(v, u);
    }
    tout[u] = timer;
}

int lca(int u, int v) {
    if(d[u] < d[v]) swap(u, v); //u is deeper
    for(int i = ln-1; i >= 0; --i) {
        if(d[u]-(1<<i) >= d[v]) {
            u = anc[u][i];
        }
    }
    if(u == v) return u;
    for(int i = ln-1; i >= 0; --i) {
        if(anc[u][i] != anc[v][i]) {
            u = anc[u][i];
            v = anc[v][i];
        }
    }
    return anc[u][0];
}

int getRoot(int u) {
    for(int i = ln-1; i >= 0; --i) { //try to go up
        if(getVal(u) == getVal(anc[u][i])) {
            u = anc[u][i];
        }
    }
    return u;
}
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, q;
    cin >> n >> m >> q;
    adj.resize(n+1);
    anc.resize(n+1, vector<int> (ln, 0));
    tin.resize(n+1);
    tout.resize(n+1);
    bit.resize(n+1, 0);
    d.resize(n+1, 0);
    d[0] = -1;
    vector<pair<int, int> > edges (1, make_pair(0, 0));
    vector<bool> edgeState (n+1, 0);
    for(int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        edges.push_back(make_pair(a, b));
    }
    dfs(1, 0);
    
    for(int i = 1; i <= n; ++i) {
        addRange(tin[i], tin[i], d[i]);
    }
    vector<int> oldValues(n+1, 0);
    vector<int> curValues (n+1, 1);
    for(int a = 0; a < m; ++a) { //proccessing events
        int cur;
        cin >> cur;
        if(edgeState[cur] == 0) { //connecting
            edgeState[cur] = 1;
            auto [x, y] = edges[cur];
            if(d[x] < d[y]) swap(x, y); //x is lower
            addRange(tin[x], tout[x], -1);
            y = getRoot(y);
            curValues[y] += curValues[x]-oldValues[x];
        }
        else {
            edgeState[cur] = 0; //disconnecting
            auto [x, y] = edges[cur];
            if(d[x] < d[y]) swap(x, y); //x is lower
            addRange(tin[x], tout[x], 1);
            y = getRoot(y);
            curValues[x] = curValues[y];
            oldValues[x] = curValues[x];
        }
    }
    for(int a = 0; a < q; ++a) {
        int cur;
        cin >> cur;
        cout << curValues[getRoot(cur)] << '\n';
    }
    return 0;
}
/*
5 6 3
1 2
1 3
2 4
2 5
1
2
1
4
4
3
1
4
5
*/

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