Submission #1082612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082612		PVSekhar	Synchronization (JOI13_synchronization)	C++14	100 / 100	671 ms	44512 KiB

synchronization

#include <bits/stdc++.h>
using namespace std; 
#define ll long long
// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 2;

int n;
vector<int> is_on;
vector<pair<int, int>> order_edges;

struct SEGTREE {
    int tree[4 * N];

    SEGTREE() {
        for (int i = 0; i < 4 * N; i++) tree[i] = 0;
    }

    void update(int node, int l, int r, int ind) {
        if (l == r) {
            tree[node] ^= 1;
            return;
        }
        int mid = (l + r) >> 1;
        if (ind <= mid) update(node << 1, l, mid, ind);
        else update(node << 1 | 1, mid + 1, r, ind);
        tree[node] = tree[node << 1] + tree[node << 1 | 1];
    }

    int query(int node, int l, int r, int i, int j) {
        if (r < i || j < l) return 0;
        if (i <= l && r <= j) return tree[node];
        int mid = (l + r) >> 1;
        return query(node << 1, l, mid, i, j) + query(node << 1 | 1, mid + 1, r, i, j);
    }

    void update(int ind) {update(1, 1, n, ind);}

    int query(int i, int j) {return query(1, 1, n, i, j);}
} segtree;

struct HLD {
    int c_ind = 1, hn[N], p[N], t[N], ind[N], sz[N], old[N], ind_nd[N], ans[N]; 
    vector<int> edges[N];

    void init() {
        sz[0] = 0;
        comp_hn(1, 0);
        do_hld(1, 0, 1);
        for (int i = 0; i < N; i++) old[i] = 0, ans[i] = 1;
    }

    void add_edge(int &x, int &y) {
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    
    void comp_hn(int node, int parent) {
        int c_hn = 0;
        p[node] = parent;
        sz[node] = 1;
        for (int child : edges[node]) {
            if (child == parent) continue;
            comp_hn(child, node);
            if (sz[child] > sz[c_hn]) c_hn = child;
        }
        hn[node] = c_hn;
    }

    void do_hld(int node, int parent, int top) {
        t[node] = top;
        ind[node] = c_ind;
        ind_nd[c_ind++] = node;
        if (hn[node]) do_hld(hn[node], node, top);
        for (int child : edges[node]) {
            if (child == parent || child == hn[node]) continue;
            do_hld(child, node, child);
        }
    }

    int lca_cc(int u) {
        int l, r, v, mid;
        while (p[u]) {
            if (!segtree.query(ind[u], ind[u])) return u;
            v = t[u];
            l = ind[v] + 1, r = ind[u];
            if (r >= l) {
                if (segtree.query(l, r) != r - l + 1) {
                    while (r - l > 1) {
                        mid = (l + r) / 2;
                        if (segtree.query(mid, r) == r - mid + 1) r = mid;
                        else l = mid;
                    }
                    return ind_nd[r - 1];
                }
            }
            if (!segtree.query(ind[v], ind[v])) return v;
            u = p[t[u]];
        }
        return u;
    }

    void query(int x) {
        int u, v, lca;
        u = order_edges[x].first;
        v = order_edges[x].second;
        if (v == p[u]) swap(u, v), order_edges[x] = make_pair(u, v);
        if (is_on[x]) {
            lca = lca_cc(v);
            ans[v] = old[v] = ans[lca];
            segtree.update(ind[v]);
        } else {
            segtree.update(ind[v]);
            lca = lca_cc(v);
            ans[lca] += ans[v] - old[v];
        }
        is_on[x] ^= 1;
    }

    void find_ans(int node) {
        cout << ans[lca_cc(node)] << "\n";
    }
} hld;

void solve() {
    int m, q, x, y;
    cin >> n >> m >> q;
    for (int i = 0; i < n - 1; i++) {
        cin >> x >> y;
        hld.add_edge(x, y);
        order_edges.push_back(make_pair(x, y));
        is_on.push_back(0);
    }
    hld.init();
    while (m--) {
        cin >> x;
        x--;
        hld.query(x);
    }
    while(q--) {
        cin >> x;
        hld.find_ans(x);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t;
    t = 1;
    // cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

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