oj.uz

Submission #824386

# Submission time Handle Problem Language Result Execution time Memory
824386 2023-08-14T05:07:38 Z Koyote Synchronization (JOI13_synchronization) C++14
100 / 100
 184 ms 29268 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 2;
int n, m, q, a[N], c[N];
int par[N], top_node[N], tin[N], subtree_size[N], node_from_time[N], tail_edge[N];
vector<pair<int, int>> adj[N];
set<int> children[N];
bitset<N> built;

void dfs_init(int u) {
    subtree_size[u] = 1;
    for (auto v : adj[u]) if (v.first != par[u]) {
        par[v.first] = u;
        tail_edge[v.second] = v.first;
        dfs_init(v.first);
        subtree_size[u] += subtree_size[v.first];
    }
}

void decompose(int u, int top) {
    top_node[u] = top;
    static int timer = 0; tin[u] = timer++;
    node_from_time[tin[u]] = u;
    children[top].insert(tin[u]);
    a[u] = 1, c[u] = 0;

    int hv = -1, hsize = 0;
    for (auto v : adj[u]) 
        if (v.first != par[u] && hsize < subtree_size[v.first])
            hv = v.first, hsize = subtree_size[v.first];
    
    if (hv != -1) decompose(hv, top);
    for (auto v : adj[u]) if (v.first != par[u] && v.first != hv)
        decompose(v.first, v.first);
}

int find_root(int u) {
    while (children[top_node[u]].upper_bound(tin[u]) == children[top_node[u]].begin())
        u = par[top_node[u]];
    return node_from_time[*(--children[top_node[u]].upper_bound(tin[u]))];
}

void insert_edge(int u) {
    int r = find_root(par[u]);
    a[r] += a[u] - c[u];
    children[top_node[u]].erase(tin[u]);
}

void remove_edge(int u) {
    int r = find_root(u);
    a[u] = c[u] = a[r];
    children[top_node[u]].insert(tin[u]);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> q;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v; --u, --v;
        adj[u].emplace_back(v, i);
        adj[v].emplace_back(u, i);
    }

    par[0] = -1;
    dfs_init(0);
    decompose(0, 0);

    while (m--) {
        int t; cin >> t; --t;
        int u = tail_edge[t];
        if (!built[u]) insert_edge(u);
        else remove_edge(u);
        built[u] = !built[u];
    }

    while (q--) {
        int u; cin >> u; --u;
        cout << a[find_root(u)] << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 4 ms 7376 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 4 ms 7520 KB Output is correct
7 Correct 10 ms 8672 KB Output is correct
8 Correct 11 ms 8764 KB Output is correct
9 Correct 12 ms 8668 KB Output is correct
10 Correct 103 ms 21112 KB Output is correct
11 Correct 106 ms 21220 KB Output is correct
12 Correct 168 ms 28440 KB Output is correct
13 Correct 74 ms 21020 KB Output is correct
14 Correct 76 ms 20644 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 24596 KB Output is correct
2 Correct 53 ms 24396 KB Output is correct
3 Correct 73 ms 27784 KB Output is correct
4 Correct 63 ms 27736 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 3 ms 7376 KB Output is correct
6 Correct 4 ms 7516 KB Output is correct
7 Correct 16 ms 9448 KB Output is correct
8 Correct 169 ms 29200 KB Output is correct
9 Correct 178 ms 29132 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 29268 KB Output is correct
2 Correct 76 ms 28876 KB Output is correct
3 Correct 76 ms 29020 KB Output is correct
4 Correct 76 ms 29008 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 13 ms 8844 KB Output is correct
7 Correct 134 ms 22168 KB Output is correct
8 Correct 184 ms 29240 KB Output is correct
9 Correct 72 ms 22080 KB Output is correct
10 Correct 92 ms 21924 KB Output is correct
11 Correct 69 ms 25832 KB Output is correct
12 Correct 64 ms 25816 KB Output is correct
13 Correct 78 ms 28940 KB Output is correct