Submission #1090207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090207		efishel	Synchronization (JOI13_synchronization)	C++17	100 / 100	290 ms	35712 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 1E5+16, LOG = 17;
ll anc[MAXN][LOG];
vii adj[MAXN];
bool isOn[MAXN];
ii edg[MAXN];
ll ans[MAXN];
ll last[MAXN];
ll tin[MAXN], tout[MAXN], timer = 0;

struct Fenwick {
    vll tree;
    ll n;

    Fenwick (ll n): tree(n), n(n) {}

    void update (ll ql, ll qr, ll val) { update(ql, val); update(qr+1, -val); }
    void update (ll id, ll val) {
        for (; id < n; id |= id+1) tree[id] += val;
    }

    ll query (ll id) {
        ll ans = 0;
        for (; id >= 0; id &= id+1, id--) ans += tree[id];
        return ans;
    }
} ft(MAXN);

void dfs (ll u, ll par) {
    tin[u] = timer++;
    anc[u][0] = par;
    for (ll bit = 1; bit < LOG; bit++) anc[u][bit] = anc[anc[u][bit-1]][bit-1];
    for (auto [v, id] : adj[u]) {
        if (v == par) continue;
        edg[id] = { u, v };
        dfs(v, u);
    }
    tout[u] = timer-1;
    ft.update(tin[u], tout[u], 1); // make the subtree have +1
}

ll findF0 (ll u, ll bit) {
    if (bit == -1) return u;
    if (ft.query(tin[anc[u][bit]]) - ft.query(tin[u]) == 0) {
        return findF0(anc[u][bit], bit-1);
    } else {
        return findF0(u, bit-1);
    }
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n, Q, qa;
    cin >> n >> Q >> qa;
    for (ll id = 1; id < n; id++) {
        ll u, v;
        cin >> u >> v;
        u--; v--;
        adj[u].push_back({ v, id });
        adj[v].push_back({ u, id });
    }
    fill(isOn, isOn+n, false);
    fill(ans, ans+n, 1);
    fill(last, last+n, 0);
    dfs(0, 0);
    auto getAns = [&](ll u) -> ll& { return ans[findF0(u, LOG-1)]; };
    while (Q--) {
        ll id;
        cin >> id;
        auto [parU, u] = edg[id];
        if (isOn[id] ^= 1) {
            ll &ansU = getAns(u);
            assert(ansU == ans[u]);
            ll &ansParU = getAns(parU);
            ll sumU = ansParU - last[id]; // how much v has grown by itself
            ll sumV = ansU - last[id]; // how much u has grown by itself
            ll newAns = last[id] + sumU + sumV;
            // ansU = newAns;
            ansParU = newAns;
            ft.update(tin[u], tout[u], -1);
        } else {
            ans[u] = last[id] = getAns(parU);
            ft.update(tin[u], tout[u], +1);
        }
    }
    while (qa--) {
        ll u;
        cin >> u;
        u--;
        cout << getAns(u) << '\n';
    }
    return 0;
}

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