Submission #1094366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094366		gyg	Synchronization (JOI13_synchronization)	C++17	100 / 100	2367 ms	26964 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vct vector
#define pii pair<int, int>
#define fir first 
#define sec second 
const int MX_N = 1e5 + 5;

int n, m, q;
arr<vct<int>, MX_N> adj;
arr<pii, MX_N> edg;

int nm_inds;
arr<int, MX_N> ind, fn_ind;
arr<arr<int, 20>, MX_N> anc;
void dfs(int u = 1) {
    nm_inds++, ind[u] = nm_inds;
    for (int v : adj[u])
        if (!ind[v]) dfs(v), anc[v][0] = u;
    fn_ind[u] = nm_inds;
}
void prcmp() {
    dfs();
    for (int i = 1; i <= 18; i++)
        for (int u = 1; u <= n; u++)
            anc[u][i] = anc[anc[u][i - 1]][i - 1];
}

arr<int, 4 * MX_N> sgtr;
void upd(int i, int x, int u = 1, int lw = 1, int hg = n) {
    if (i < lw || hg < i) return;
    if (lw == hg) { sgtr[u] += x; return; }
    int md = (lw + hg) / 2;
    upd(i, x, 2 * u, lw, md), upd(i, x, 2 * u + 1, md + 1, hg);
    sgtr[u] = sgtr[2 * u] + sgtr[2 * u + 1];
}
int qry(int l, int r, int u = 1, int lw = 1, int hg = n) {
    if (r < lw || hg < l) return 0;
    if (l <= lw && hg <= r) return sgtr[u];
    int md = (lw + hg) / 2;
    return qry(l, r, 2 * u, lw, md) + qry(l, r, 2 * u + 1, md + 1, hg); 
}
void trn_on(int u) { upd(ind[u], -1), upd(fn_ind[u] + 1, +1); }
void trn_off(int u) { upd(ind[u], +1), upd(fn_ind[u] + 1, -1); }
int qry_pth(int u, int v) { return qry(1, ind[v]) - qry(1, ind[u]); } 
int gt_pr(int u) {
    int v = u;
    for (int i = 18; i >= 0; i--)
        if (anc[v][i] != 0 && qry_pth(anc[v][i], u) == 0)
            v = anc[v][i];
    return v;
}

arr<bool, MX_N> on;
arr<int, MX_N> vl, lst;
void ins(int u) {
    assert(u != 1);
    int pr_vl = vl[gt_pr(u)] + vl[gt_pr(anc[u][0])] - lst[u];
    trn_on(u);
    vl[gt_pr(u)] = pr_vl;
}
void dlt(int u) {
    lst[u] = vl[gt_pr(u)];
    trn_off(u);
    vl[gt_pr(u)] = vl[gt_pr(anc[u][0])] = lst[u];
}

int main() {
    // freopen("sync.in", "r", stdin);
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        cin >> edg[i].fir >> edg[i].sec;
        adj[edg[i].fir].push_back(edg[i].sec);
        adj[edg[i].sec].push_back(edg[i].fir);
    } 

    prcmp();
    for (int u = 2; u <= n; u++) trn_off(u);
    for (int u = 1; u <= n; u++) vl[u] = 1;

    for (int i = 1; i <= m; i++) {
        int j; cin >> j;
        int u = (anc[edg[j].fir][0] == edg[j].sec) ? edg[j].fir : edg[j].sec;
        
        if (!on[u]) on[u] = true, ins(u);
        else on[u] = false, dlt(u);
        
        // for (int v = 1; v <= n; v++) cout << v << "," << gt_pr(v) << " ";
        // for (int v = 1; v <= n; v++) cout << vl[gt_pr(v)] << " ";
        // cout << endl;
    }

    for (int i = 1; i <= q; i++) {
        int u; cin >> u;
        cout << vl[gt_pr(u)] << '\n';
    }
}

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