Submission #1188254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188254		duckindog	Synchronization (JOI13_synchronization)	C++17	100 / 100	106 ms	20808 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int n, m, q;
pair<int, int> edge[N];
vector<int> ad[N];

int sz[N];
void dfs(int u, int p = -1) { 
    sz[u] = 1;
    for (int v : ad[u]) { 
        if (v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int head[N], par[N];
int st[N], ed[N], node[N], num;
void hld(int u, int p = -1) { 
    if (!head[u]) head[u] = u;
    st[u] = ++num; node[num] = u;

    sort(ad[u].begin(), ad[u].end(), [&](int a, int b) { 
        return sz[a] > sz[b];
    });
    bool goHeavy = false;
    for (const auto& v : ad[u]) { 
        if (v == p) continue;
        if (!goHeavy) goHeavy = true, head[v] = head[u];
        par[v] = u;
        hld(v, u);
    }

    ed[u] = num;
}

namespace BIT { 
    int bit[N];
    inline void upd(int i, int x) { 
        for (; i <= n; i += i & -i) bit[i] += x;
    }
    inline int que(int i) { 
        int ret = 0;
        for (; i; i -= i & -i) ret += bit[i];
        return ret;
    }
    inline int que(int l, int r) { return que(r) - que(l - 1); }
}
inline int root(int u) { 
    while (u != 1) { 
        int x = head[u];

        if (st[u] - st[x] + 1 == BIT::que(st[x], st[u])) {
            u = par[head[u]];
            continue;
        }
        
        int uSum = BIT::que(st[u]);

        int pos = 0, sum = 0;
        for (int i = 16; i >= 0; --i) { 
            int nPos = pos + (1 << i), nSum = sum + BIT::bit[nPos];
            if (nPos > st[u]) continue;
            if (uSum - nSum == st[u] - nPos) continue;
            tie(pos, sum) = {nPos, nSum};
        }
        if (pos == st[u]) return node[pos];
        return node[pos + 1];
    }
    return 1;
}

bool isCon[N];
int answer[N], cAnswer[N];

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        edge[i] = {u, v};
        ad[u].push_back(v);
        ad[v].push_back(u);
    }    

    dfs(1);
    hld(par[1] = 1);

    for (int i = 1; i < n; ++i) { 
        auto& [u, v] = edge[i];
        if (st[u] > st[v]) swap(u, v);
    }
    fill(answer + 1, answer + n + 1, 1);

    while (m--) { 
        int idx; cin >> idx;

        auto [u, v] = edge[idx];
        isCon[idx] ^= 1;

        if (isCon[idx]) { 
            u = root(u);
            BIT::upd(st[v], 1);
            answer[u] = answer[u] + answer[v] - cAnswer[idx];
        } else { 
            BIT::upd(st[v], -1);
            u = root(u);
            answer[v] = cAnswer[idx] = answer[u];
        }
    }

    while (q--) { 
        int u; cin >> u;
        cout << answer[root(u)] << "\n";
    }
}

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