oj.uz

Submission #824134

# Submission time Handle Problem Language Result Execution time Memory
824134 2023-08-13T15:11:20 Z Koyote Synchronization (JOI13_synchronization) C++14
100 / 100
 175 ms 29228 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;

const int N = 1e5 + 2;
int n, m, q;
int par[N], par_edge[N], subtree_size[N], top_node[N], tin[N], node_id[N];
vector<ii> adj[N];
set<int> roots[N];
int a[N], c[N];
bitset<N> built;

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

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

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

    if (hv != -1) decompose(hv, top);

    for (auto nei : adj[u]) {
        int v = nei.first;
        if (v != par[u] && v != hv) decompose(v, v);
    }
}

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

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

void delete_edge(int u) {
    int r = find_root(u);
    a[u] = c[u] = a[r];
    roots[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 = par_edge[t];
        if (!built[u]) insert_edge(u);
        else delete_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 4 ms 7380 KB Output is correct
2 Correct 4 ms 7384 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 7380 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 10 ms 8672 KB Output is correct
8 Correct 10 ms 8768 KB Output is correct
9 Correct 10 ms 8668 KB Output is correct
10 Correct 108 ms 21216 KB Output is correct
11 Correct 116 ms 21216 KB Output is correct
12 Correct 161 ms 28436 KB Output is correct
13 Correct 79 ms 20920 KB Output is correct
14 Correct 85 ms 20640 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 24584 KB Output is correct
2 Correct 53 ms 24396 KB Output is correct
3 Correct 63 ms 27852 KB Output is correct
4 Correct 72 ms 27792 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 3 ms 7352 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 3 ms 7376 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 20 ms 9520 KB Output is correct
8 Correct 171 ms 29200 KB Output is correct
9 Correct 170 ms 29196 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 29228 KB Output is correct
2 Correct 78 ms 28876 KB Output is correct
3 Correct 91 ms 29044 KB Output is correct
4 Correct 78 ms 28988 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 3 ms 7384 KB Output is correct
5 Correct 4 ms 7544 KB Output is correct
6 Correct 12 ms 8788 KB Output is correct
7 Correct 134 ms 22092 KB Output is correct
8 Correct 175 ms 29208 KB Output is correct
9 Correct 79 ms 22088 KB Output is correct
10 Correct 97 ms 21828 KB Output is correct
11 Correct 67 ms 25804 KB Output is correct
12 Correct 68 ms 25800 KB Output is correct
13 Correct 77 ms 28944 KB Output is correct