oj.uz

Submission #1082612

# Submission time Handle Problem Language Result Execution time Memory
1082612 2024-08-31T18:06:50 Z PVSekhar Synchronization (JOI13_synchronization) C++14
100 / 100
 671 ms 44512 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 5468 KB Output is correct
4 Correct 1 ms 5468 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 13 ms 6488 KB Output is correct
8 Correct 16 ms 6112 KB Output is correct
9 Correct 13 ms 8028 KB Output is correct
10 Correct 164 ms 14000 KB Output is correct
11 Correct 153 ms 14024 KB Output is correct
12 Correct 524 ms 43712 KB Output is correct
13 Correct 99 ms 13980 KB Output is correct
14 Correct 110 ms 13576 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 28868 KB Output is correct
2 Correct 99 ms 28448 KB Output is correct
3 Correct 198 ms 43212 KB Output is correct
4 Correct 198 ms 43208 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Correct 1 ms 5568 KB Output is correct
3 Correct 2 ms 5468 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Correct 1 ms 5468 KB Output is correct
6 Correct 4 ms 5720 KB Output is correct
7 Correct 46 ms 9100 KB Output is correct
8 Correct 600 ms 44512 KB Output is correct
9 Correct 612 ms 44480 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 671 ms 44484 KB Output is correct
2 Correct 340 ms 43980 KB Output is correct
3 Correct 349 ms 44264 KB Output is correct
4 Correct 347 ms 44208 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5464 KB Output is correct
2 Correct 1 ms 7260 KB Output is correct
3 Correct 2 ms 5544 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 3 ms 5468 KB Output is correct
6 Correct 16 ms 6480 KB Output is correct
7 Correct 199 ms 15044 KB Output is correct
8 Correct 630 ms 44472 KB Output is correct
9 Correct 126 ms 15040 KB Output is correct
10 Correct 296 ms 14788 KB Output is correct
11 Correct 115 ms 29896 KB Output is correct
12 Correct 117 ms 29984 KB Output is correct
13 Correct 337 ms 44224 KB Output is correct