Submission #1090197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090197		efishel	Synchronization (JOI13_synchronization)	C++17	10 / 100	8061 ms	16008 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;
vii adj[MAXN];
bool isOn[MAXN];
ii edg[MAXN];
ll ans[MAXN];
ii last[MAXN];

void dfs (ll u, ll par, ll add) {
    ans[u] += add;
    for (auto [v, id] : adj[u]) {
        if (v == par || !isOn[id]) continue;
        dfs(v, u, add);
    }
}

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 });
        edg[id] = { u, v };
    }
    fill(isOn, isOn+n, false);
    fill(ans, ans+n, 1);
    fill(last, last+n, ii{ 0, 0 });
    while (Q--) {
        ll id;
        cin >> id;
        auto [u, v] = edg[id];
        if (isOn[id] ^= 1) {
            ll sumU = ans[v] - last[id].second; // how much v has grown
            ll sumV = ans[u] - last[id].first; // how much u has grown
            dfs(u, v, sumU);
            dfs(v, u, sumV);
        } else {
            last[id] = ii{ ans[u], ans[v] };
        }
    }
    while (qa--) {
        ll u;
        cin >> u;
        u--;
        cout << ans[u] << '\n';
    }
    return 0;
}

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