oj.uz

Submission #599893

# Submission time Handle Problem Language Result Execution time Memory
599893 2022-07-20T06:27:02 Z timmyfeng Synchronization (JOI13_synchronization) C++17
100 / 100
 264 ms 36416 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5;

int node[N], parent[N], sub[N], in[N];
vector<pair<int, int>> adj[N];

void dfs_sub(int u) {
    sub[u] = 1;
    for (auto &e : adj[u]) {
        auto [c, i] = e;
        parent[c] = u, node[i] = c;
        adj[c].erase(find(adj[c].begin(), adj[c].end(), pair<int, int>{u, i}));
        dfs_sub(c);
        sub[u] += sub[c];
        if (sub[c] > sub[adj[u][0].first]) {
            swap(adj[u][0], e);
        }
    }
}

int head[N], tour[N];

void dfs_hld(int u) {
    static int t = 0;
    tour[t] = u, in[u] = t++;
    for (auto [c, i] : adj[u]) {
        head[c] = (c == adj[u][0].first) ? head[u] : c;
        dfs_hld(c);
    }
}

set<int> off[N];

int get_root(int u) {
    while (off[head[u]].empty() || *off[head[u]].begin() > in[u]) {
        u = parent[head[u]];
    }
    return tour[*--off[head[u]].upper_bound(in[u])];
}

int answer[N], common[N];
bool on[N];

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

    int n, m, q; cin >> n >> m >> q;

    for (int i = 0; i < n - 1; ++i) {
        int u, v; cin >> u >> v; --u, --v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    dfs_sub(0), dfs_hld(0);

    for (int i = 0; i < n; ++i) {
        off[head[i]].insert(in[i]);
        answer[i] = 1;
    }

    for (int i = 0; i < m; ++i) {
        int d; cin >> d; --d;

        if (!on[d]) {
            int u = node[d], v = get_root(parent[u]);
            answer[v] += answer[u] - common[u];

            off[head[u]].erase(in[u]);
            on[d] = true;
        } else {
            int u = node[d], v = get_root(u);
            answer[u] = common[u] = answer[v];

            off[head[u]].insert(in[u]);
            on[d] = false;
        }
    }

    for (int i = 0; i < q; ++i) {
        int c; cin >> c; --c;
        cout << answer[get_root(c)] << "\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14548 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14348 KB Output is correct
4 Correct 7 ms 14408 KB Output is correct
5 Correct 7 ms 14404 KB Output is correct
6 Correct 9 ms 14572 KB Output is correct
7 Correct 17 ms 15748 KB Output is correct
8 Correct 17 ms 15724 KB Output is correct
9 Correct 17 ms 15700 KB Output is correct
10 Correct 177 ms 28324 KB Output is correct
11 Correct 187 ms 28368 KB Output is correct
12 Correct 189 ms 35600 KB Output is correct
13 Correct 88 ms 28100 KB Output is correct
14 Correct 131 ms 27360 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 31720 KB Output is correct
2 Correct 72 ms 31320 KB Output is correct
3 Correct 79 ms 34716 KB Output is correct
4 Correct 87 ms 34708 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14468 KB Output is correct
2 Correct 10 ms 14412 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14388 KB Output is correct
6 Correct 9 ms 14576 KB Output is correct
7 Correct 24 ms 16524 KB Output is correct
8 Correct 220 ms 36400 KB Output is correct
9 Correct 264 ms 36416 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 36308 KB Output is correct
2 Correct 109 ms 35712 KB Output is correct
3 Correct 105 ms 35828 KB Output is correct
4 Correct 97 ms 35852 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 10 ms 14440 KB Output is correct
3 Correct 8 ms 14436 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 9 ms 14540 KB Output is correct
6 Correct 18 ms 15856 KB Output is correct
7 Correct 193 ms 29156 KB Output is correct
8 Correct 213 ms 36408 KB Output is correct
9 Correct 118 ms 29244 KB Output is correct
10 Correct 135 ms 28716 KB Output is correct
11 Correct 84 ms 32732 KB Output is correct
12 Correct 85 ms 32656 KB Output is correct
13 Correct 104 ms 35900 KB Output is correct