oj.uz

Submission #402756

# Submission time Handle Problem Language Result Execution time Memory
402756 2021-05-12T10:39:12 Z two_sides Synchronization (JOI13_synchronization) C++17
100 / 100
 308 ms 26256 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;
const int LOG = 17;

int tin[MAXN], tout[MAXN];
int BIT[MAXN]; bool stat[MAXN];
pair <int, int> edge[MAXN];
vector <pair <int, int>> adj[MAXN];
int anc[MAXN][LOG];
int last[MAXN], val[MAXN];

void add(int i, int v) {
    for (i++; i < MAXN; i += i & -i)
        BIT[i] += v;
}

int sum(int i) {
    int sum = 0;
    for (i++; i > 0; i -= i & -i)
        sum += BIT[i];
    return sum;
}

int root(int u) {
    for (int i = LOG; --i >= 0; ) {
        if (anc[u][i] && sum(tin[u])
        == sum(tin[anc[u][i]]))
            u = anc[u][i];
    }
    return u;
}

void DFS(int u) {
    static int timer = 0;
    tin[u] = timer++;
    for (int i = 0; ++i < LOG; )
        anc[u][i] = anc[anc[u][i - 1]][i - 1];
    for (auto e : adj[u]) {
        int v, i; tie(v, i) = e;
        if (v != anc[u][0]) {
            anc[v][0] = u;
            edge[i] = {u, v}; DFS(v);
        }
    }
    tout[u] = timer; val[u] = 1;
    add(tin[u], -1); add(tout[u], 1);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int N, M, Q;
    cin >> N >> M >> Q;
    for (int i = 1; i < N; i++) {
        int u, v; cin >> u >> v;
        adj[u].emplace_back(v, i);
        adj[v].emplace_back(u, i);
    }
    DFS(1);
    while (M--) {
        int i, u, v; cin >> i;
        tie(u, v) = edge[i];
        if (stat[i]) {
            last[v] = val[v] = val[root(u)];
            add(tin[v], -1); add(tout[v], 1);
        } else {
            val[root(u)] += val[v] - last[v];
            add(tin[v], 1); add(tout[v], -1);
        }
        stat[i] ^= 1;
    }
    while (Q--) {
        int u; cin >> u;
        cout << val[root(u)] << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2676 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2676 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 15 ms 4240 KB Output is correct
8 Correct 14 ms 4172 KB Output is correct
9 Correct 14 ms 4240 KB Output is correct
10 Correct 189 ms 18088 KB Output is correct
11 Correct 180 ms 18128 KB Output is correct
12 Correct 236 ms 25384 KB Output is correct
13 Correct 81 ms 17976 KB Output is correct
14 Correct 133 ms 17220 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 21312 KB Output is correct
2 Correct 92 ms 21112 KB Output is correct
3 Correct 111 ms 24416 KB Output is correct
4 Correct 110 ms 24456 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 4 ms 2892 KB Output is correct
7 Correct 21 ms 4992 KB Output is correct
8 Correct 294 ms 26140 KB Output is correct
9 Correct 308 ms 26256 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 26256 KB Output is correct
2 Correct 179 ms 25516 KB Output is correct
3 Correct 173 ms 25588 KB Output is correct
4 Correct 177 ms 25620 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2672 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 4 ms 2764 KB Output is correct
6 Correct 20 ms 4300 KB Output is correct
7 Correct 256 ms 18996 KB Output is correct
8 Correct 308 ms 26144 KB Output is correct
9 Correct 108 ms 18996 KB Output is correct
10 Correct 171 ms 18424 KB Output is correct
11 Correct 126 ms 22508 KB Output is correct
12 Correct 124 ms 22592 KB Output is correct
13 Correct 186 ms 25652 KB Output is correct