Submission #1307949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307949		vk3601h	Synchronization (JOI13_synchronization)	C++20	100 / 100	276 ms	32320 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;

template <typename _Tp>
class SumSegmentTree{
private:
    int size;
    vector<_Tp> segtree;
    vector<_Tp> lazy;

    void apply(int at, int at_left, int at_right, _Tp val){
        segtree[at] += (at_right - at_left + 1) * val;
        lazy[at] += val;
    }

    void push_down(int at, int at_left, int at_right){
        if (at_left < at_right && lazy[at] != 0){
            int mid = (at_left + at_right) / 2;
            apply(2 * at, at_left, mid, lazy[at]);
            apply(2 * at + 1, mid + 1, at_right, lazy[at]);
            lazy[at] = 0;
        }
    }

    void build(const _Tp DEFAULT, int at, int at_left, int at_right){
        if (at_left == at_right){
            segtree[at] = DEFAULT;
            return;
        }

        int mid = (at_left + at_right) / 2;
        build(DEFAULT, 2 * at, at_left, mid);
        build(DEFAULT, 2 * at + 1, mid + 1, at_right);
        segtree[at] = segtree[2 * at] + segtree[2 * at + 1];
    }

    void node_add(int ind, _Tp val, int at, int at_left, int at_right){
        if (at_left == at_right){
            apply(at, at_left, at_right, val);
            return;
        }
        push_down(at, at_left, at_right);

        int mid = (at_left + at_right) / 2;
        if (ind <= mid) node_add(ind, val, 2 * at, at_left, mid);
        else node_add(ind, val, 2 * at + 1, mid + 1, at_right);
        segtree[at] = segtree[2 * at] + segtree[2 * at + 1];
    }

    void range_add(int start, int end, _Tp val, int at, int at_left, int at_right){
        if (end < at_left || at_right < start) return;
        if (start <= at_left && at_right <= end){
            apply(at, at_left, at_right, val);
            return;
        }
        push_down(at, at_left, at_right);

        int mid = (at_left + at_right) / 2;
        range_add(start, end, val, 2 * at, at_left, mid);
        range_add(start, end, val, 2 * at + 1, mid + 1, at_right);
        segtree[at] = segtree[2 * at] + segtree[2 * at + 1];
    }

    _Tp query(int ind, int at, int at_left, int at_right){
        if (at_left == at_right) return segtree[at];
        push_down(at, at_left, at_right);

        int mid = (at_left + at_right) / 2;
        if (ind <= mid) return query(ind, 2 * at, at_left, mid);
        return query(ind, 2 * at + 1, mid + 1, at_right);
    }

public:
    SumSegmentTree(int _size, const _Tp DEFAULT = 1) : size(_size), segtree(size * 4), lazy(size * 4, 0) {
        build(DEFAULT, 1, 0, size - 1);
    }

    void node_add(int ind, _Tp val) {node_add(ind, val, 1, 0, size - 1);}

    void range_add(int start, int end, _Tp val) {range_add(start, end, val, 1, 0, size - 1);}

    _Tp query(int ind) {return query(ind, 1, 0, size - 1);}
};

template <typename _Tp>
class MaxSegmentTree{
private:
    int size;
    vector<_Tp> segtree;

    void build(int at, int at_left, int at_right){
        if (at_left == at_right){
            segtree[at] = at_left;
            return;
        }

        int mid = (at_left + at_right) / 2;
        build(2 * at, at_left, mid);
        build(2 * at + 1, mid + 1, at_right);
        segtree[at] = max(segtree[2 * at], segtree[2 * at + 1]);
    }

    void modify(int ind, _Tp val, int at, int at_left, int at_right){
        if (at_left == at_right){
            segtree[at] = val;
            return;
        }

        int mid = (at_left + at_right) / 2;
        if (ind <= mid) modify(ind, val, 2 * at, at_left, mid);
        else modify(ind, val, 2 * at + 1, mid + 1, at_right);
        segtree[at] = max(segtree[2 * at], segtree[2 * at + 1]);
    }

    _Tp query(int start, int end, int at, int at_left, int at_right){
        if (end < at_left || at_right < start) return -1;
        if (start <= at_left && at_right <= end) return segtree[at];

        int mid = (at_left + at_right) / 2;
        return max(query(start, end, 2 * at, at_left, mid), query(start, end, 2 * at + 1, mid + 1, at_right));
    }

public:
    MaxSegmentTree(int _size) : size(_size), segtree(size * 4) {
        build(1, 0, size - 1);
    }

    void modify(int ind, _Tp val) {modify(ind, val, 1, 0, size - 1);}

    _Tp query(int start, int end) {return query(start, end, 1, 0, size - 1);}
};

class Solver{
private:
    const vector<vector<int>> &adj;
    vector<int> parent, depth, heavy, head, pos, old;
    SumSegmentTree<int> segtree;
    MaxSegmentTree<int> top;

    int dfs(int curr){
        int size = 1, max_c_size = 0;
        for (int child : adj[curr]){
            if (child != parent[curr]){
                parent[child] = curr;
                depth[child] = depth[curr] + 1;

                int c_size = dfs(child);
                size += c_size;
                if (c_size > max_c_size){
                    max_c_size = c_size;
                    heavy[curr] = child;
                }
            }
        }
        return size;
    }

    void decompose(int curr, int curr_head, int &timer){
        head[curr] = curr_head;
        pos[curr] = timer;
        timer++;

        if (heavy[curr] != -1) decompose(heavy[curr], curr_head, timer);
        for (int child : adj[curr]) if (child != parent[curr] && child != heavy[curr]) decompose(child, child, timer);
    }

public:
    Solver(const vector<vector<int>> &_adj) : adj(_adj), parent(adj.size()), depth(adj.size()), heavy(adj.size(), -1), head(adj.size()), pos(adj.size()), old(adj.size(), 0), segtree(adj.size()), top(adj.size()) {
        parent[0] = -1;
        depth[0] = 0;
        dfs(0);

        int timer = 0;
        decompose(0, 0, timer);
    }

    void connect(int u, int v){
        if (depth[u] > depth[v]) swap(u, v);
        top.modify(pos[v], -1);

        int curr = u, contrib = segtree.query(pos[v]) - old[v];
        while (curr >= 0){
            int curr_top = top.query(pos[head[curr]], pos[curr]);
            segtree.range_add((curr_top == -1 ? pos[head[curr]] : curr_top), pos[curr], contrib);
            if (curr_top != -1) break;
            curr = parent[head[curr]];
        }
    }

    void disconnect(int u, int v){
        if (depth[u] > depth[v]) swap(u, v);
        top.modify(pos[v], pos[v]);

        int curr = u;
        while (curr >= 0){
            int curr_top = top.query(pos[head[curr]], pos[curr]);
            if (curr_top >= 0){
                curr = curr_top;
                break;
            }
            curr = parent[head[curr]];
        }

        int contrib = segtree.query(curr) - segtree.query(pos[v]);
        segtree.node_add(pos[v], contrib);
        old[v] = segtree.query(pos[v]);
    }

    int query(int node){
        int curr = node;
        while (curr >= 0){
            int curr_top = top.query(pos[head[curr]], pos[curr]);
            if (curr_top >= 0){
                curr = curr_top;
                break;
            }
            curr = parent[head[curr]];
        }
        return segtree.query(curr);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int node_num, op_num, query_num;
    cin >> node_num >> op_num >> query_num;

    vector<pair<int, int>> edges(node_num - 1);
    vector<vector<int>> adj(node_num);
    for (int i = 0; i < node_num - 1; i++){
        int u, v;
        cin >> u >> v;
        u--, v--;
        edges[i] = {u, v};
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    Solver solver(adj);

    vector<bool> state(node_num - 1, false);
    while (op_num--){
        int ind;
        cin >> ind;
        ind--;

        if (!state[ind]){
            solver.connect(edges[ind].first, edges[ind].second);
            state[ind] = true;
        }
        else {
            solver.disconnect(edges[ind].first, edges[ind].second);
            state[ind] = false;
        }
    }

    while (query_num--){
        int node;
        cin >> node;
        cout << solver.query(node - 1) << "\n";
    }

    return 0;
}

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