Submission #1184752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184752		tin_le	Synchronization (JOI13_synchronization)	C++20	30 / 100	252 ms	57652 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
 
// shorthand
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vpii = vector<pii>;
template<class T> using vt = vector<T>;
 
// ------------------- FW (Fenwick Tree) for 1-indexed arrays -----------------------
template<class T, typename F = function<T(const T&, const T&)>>
class FW {
public:
    int n, N;
    vt<T> tree;    
    T DEFAULT;
    F func;
    FW() {}
    // n here is the maximum valid index (1-indexed), so we create tree[1..n]
    FW(int n, T DEFAULT, F func) : func(func) { 
        this->n = n;
        this->DEFAULT = DEFAULT;
        // we'll allocate vector of size n+1 so that indices 1..n are used.
        tree.resize(n + 1, DEFAULT);
        N = floor(log2(n)) + 1; // for select, if needed.
    }
    
    // update_at: add val at index id (id between 1 and n)
    void update_at(int id, T val) {  
        assert(id >= 1);
        for(; id <= n; id += id & -id)
            tree[id] = func(tree[id], val);
    }
    
    // get: prefix sum from 1 to id.
    T get(int id) {   
        assert(id >= 1 && id <= n);
        T res = DEFAULT;
        for(; id; id -= id & -id)
            res = func(res, tree[id]);
        return res;
    }
 
    // queries_range: sum in [l, r] (1-indexed)
    T queries_range(int l, int r) {  
        if(l > r) return DEFAULT;
        return get(r) - (l > 1 ? get(l - 1) : 0);
    }
 
    T queries_at(int i) {
        return queries_range(i, i);
    }
 
    // update_range: add val to each index in [l, r]
    void update_range(int l, int r, T val) {
        update_at(l, val);
        if(r + 1 <= n)
            update_at(r + 1, -val);
    }
	
	void reset() {
		tree.assign(n + 1, DEFAULT);
	}
 
    int select(int x) { // get pos where prefix sum >= x
        int global = get(n), curr = 0;
        for(int i = N; i >= 0; i--) {
            int t = curr + (1 << i);
            if(t <= n && get(t) < x) {
                curr = t;
            }
        }
        return curr + 1;
    }
};
 
// ------------------- LCA_O1 (LCA using Euler Tour & Sparse Table) for 1-indexed nodes -----------------------
template<typename T = int>
struct LCA_O1 {
    vector<int> enter;
    vpii euler;
    vector<vector<pii>> st;
    vector<int> log_table;
    int timer;
    LCA_O1() {}
    // here graph is 1-indexed; we assume nodes from 1 to n.
    LCA_O1(const vt<vt<T>> &graph, int root = 1) : timer(1) { 
        int n = graph.size() - 1; // graph[1..n]
        enter.resize(n + 1, -1);
        dfs(root, -1, 0, graph);
        int m = euler.size();
        log_table.resize(m + 1);
        for (int i = 2; i <= m; i++) log_table[i] = log_table[i / 2] + 1;
        int K = log_table[m] + 1;
        st.assign(K, vector<pii>(m));
        for (int i = 0; i < m; i++) st[0][i] = euler[i];
        for (int j = 1; j < K; j++) {
            for (int i = 0; i + (1 << j) <= m; i++) {
                pii a = st[j - 1][i], b = st[j - 1][i + (1 << (j - 1))];
                st[j][i] = (a.first < b.first ? a : b);
            }
        }
    }
    void dfs(int node, int par, int d, const vt<vt<T>> &graph) {
        enter[node] = timer;
        euler.push_back({d, node});
        for(auto nxt : graph[node]) {
            if(nxt == par) continue;
            dfs(nxt, node, d + 1, graph);
            euler.push_back({d, node});
            timer++;
        }
        timer++;
    }
    int lca(int u, int v) {
        int L = min(enter[u], enter[v]);
        int R = max(enter[u], enter[v]);
        int j = log_table[R - L + 1];
        pii a = st[j][L - 1], b = st[j][R - (1 << j) + 1 - 1];
        return (a.first < b.first ? a : b).second;
    }
};
 
// ------------------- GRAPH Class for 1-indexed nodes -----------------------
template<typename T = int>
class GRAPH { 
public: 
    int n, m; 
    vvi dp;
    vi depth, parent, subtree;
    vi tin, tout, ord;
    int timer = 1;
    LCA_O1<T> lca_01;
    GRAPH() {}
 
    // graph is given as 1-indexed: indices 1..n, graph[0] is unused.
    GRAPH(const vt<vt<T>>& graph, int root = 1) : lca_01(graph, root) {   
        n = graph.size() - 1;
        m = log2(n) + 1;
        dp.resize(n + 1, vi(m, root)); // dp[1..n]
        depth.resize(n + 1, 0);
        parent.resize(n + 1, -1);
		subtree.resize(n + 1, 1);
        tin.resize(n + 1);
        tout.resize(n + 1);
		ord.resize(n + 1);
        dfs(graph, root, -1);
        init();
    }
    
    // DFS: node from 1..n; par = -1 for root.
    void dfs(const vt<vt<T>>& graph, int node, int par) {   
		tin[node] = timer++;
		ord[tin[node]] = node;
        for(auto nxt : graph[node]) {  
            if(nxt == par) continue;    
            depth[nxt] = depth[node] + 1;   
            dp[nxt][0] = node;
            parent[nxt] = node;
			dfs(graph, nxt, node);
			subtree[node] += subtree[nxt];
        }
		tout[node] = timer - 1;
    }
 
    bool isAncestor(int u, int v) { 
        return tin[u] <= tin[v] && tin[v] <= tout[u]; 
    }
    
    void init() {  
        for(int j = 1; j < m; j++) {   
            for(int i = 1; i <= n; i++) {    
                dp[i][j] = dp[dp[i][j - 1]][j - 1];
            }
        }
    }
	
    int lca(int a, int b) { 
        return lca_01.lca(a, b);
    }
	
	int dist(int u, int v) {    
        int a = lca(u, v);  
        return depth[u] + depth[v] - 2 * depth[a];
    }
 
    int k_ancestor(int a, int k) {
        for(int i = m - 1; i >= 0; i--) {   
            if((k >> i) & 1) a = dp[a][i];
        }
        return a;
    }
};
 
// ------------------- FW for 1-indexed BIT already defined above -----------------------
 
// ------------------- Main solve() for 1-indexed system -----------------------
const int MK = 20;
 
void solve() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, m, q; 
    cin >> n >> m >> q;
    // We'll work with nodes 1..n
    // Allocate graph with size n+1 (ignore index 0)
    vt<vt<int>> graph(n + 1);
    vpii edges(n); // edges[1..n-1]
    for (int i = 1; i <= n - 1; i++) {
        int u, v; 
        cin >> u >> v;
        // assume input is 1-indexed; no conversion needed.
        edges[i] = {u, v};
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    // Build GRAPH with root = 1.
    GRAPH<int> g(graph, 1);
    // Reorient edges so that for each edge, the first is the parent and the second is the child.
    for (int i = 1; i <= n - 1; i++) {
        auto &e = edges[i];
        int u = e.first, v = e.second;
        if(g.parent[v] != u) swap(u, v);
        e = {u, v};
    }
 
    // Build BIT (FW) with size n, for Euler tour indices in [1, n].
    FW<int> BITree(n, 0, [](const int &a, const int &b) { return a + b; });
    // Initialize BIT: for every node i (1-indexed), update at position tin[i] with +1.
    for (int i = 1; i <= n; i++) {
        BITree.update_at(g.tin[i], 1);
    }
 
    // Use the full dp table size for binary lifting.
    int liftSize = g.dp[1].size();  // dp[1]..dp[n]
    auto find_par = [&](int u) -> int {
        int x = BITree.get(g.tin[u]);
        for (int j = liftSize - 1; j >= 0; j--) {
            int p = g.dp[u][j];
            if(p < 1 || p > n) continue;
            // Here we use >= in case updates cause BIT value to become larger
            if(BITree.get(g.tin[p]) >= x)
                u = p;
        }
        return u;
    };
 
    // used[] for edge toggling; initialize ans[] to 1 for every node; del[] as auxiliary.
    vi used(n, 0), ans(n + 1, 1), del(n + 1, 0);
    // Process m operations (edge toggles).
    // Edge ids are given 1-indexed.
    for (int i = 1; i <= m; i++) {
        int k; 
        cin >> k;
        // k is between 1 and n-1.
        auto &e = edges[k];
        int u = e.first, v = e.second;
        if(!used[k]) { // Remove edge: cut subtree v from u.
            ans[find_par(u)] += ans[v] - del[v]; 
            BITree.update_range(g.tin[v], g.tout[v], -1);
        } else { // Add edge: merge subtree v back with u.
            ans[v] = del[v] = ans[find_par(u)];
            BITree.update_range(g.tin[v], g.tout[v], 1);
        }
        used[k] ^= 1;
    }
 
    // Process q queries: for each query node u (1-indexed), output the aggregate of its component.
    while(q--) {
        int u; 
        cin >> u;
        assert(u >= 1 && u <= n);
        cout << ans[find_par(u)] << "\n";
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

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