Submission #819380

#	Time	Username	Problem	Language	Result	Execution time	Memory
819380		boyliguanhan	Synchronization (JOI13_synchronization)	C++17	100 / 100	229 ms	24240 KiB

synchronization

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
bool on[100100];
vector<int> adj[100100];
int ans[100100], pre[100100], cnt = 1, ti[100100], to[100100], bj[100100][20], tree[100100], E[200100][2];
void dfs(int n, int p) {
    bj[n][0] = p;
    for (int i = 1; i < 20; i++)
        bj[n][i] = bj[bj[n][i - 1]][i - 1];
    ans[n] = 1;
    ti[n] = cnt++;
    for (int i : adj[n])
        if (i-p)
            dfs(i, n);
    to[n] = cnt;
}
void U(int n, int val) {
    while(n < 100100)
        tree[n] += val, n+=n&-n;
}
int Q(int n) {
    int ans = 0;
    while(n)
        ans += tree[n], n-=n&-n;
    return ans;
}
int gr(int n) {
    int lca = n;
    for (int i = 20; i--;)
        if (Q(ti[bj[lca][i]]) == Q(ti[n]))
            lca = bj[lca][i];
    return lca;
}
int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++) {
        cin >> E[i][0] >> E[i][1];
        adj[E[i][0]].push_back(E[i][1]);
        adj[E[i][1]].push_back(E[i][0]);
    }
    dfs(1,1);
    for(int i = 1; i < n; i++) {
        if(bj[E[i][0]][0]==E[i][1])
            swap(E[i][0], E[i][1]);
    }
    for(int i = 1; i <= n; i++) {
        U(ti[i], -1);
        U(to[i], 1);
    }
    while (m--) {
        int x;
        cin >> x;
        int u = E[x][0], v = E[x][1];
        if (bj[u][0] == v) swap(u, v);
                if (on[x]) {
            ans[v] = pre[v] = ans[gr(u)];
            U(ti[v], -1);
            U(to[v], 1);
        } else {
            ans[gr(u)] += ans[v] - pre[v];
            U(ti[v], 1);
            U(to[v], -1);
        }
        on[x] = !on[x];
    }
    while (q--) {
        int x;
        cin >> x;
        cout << ans[gr(x)] << '\n';
    }
    return 0;
}

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