oj.uz

Submission #466832

# Submission time Handle Problem Language Result Execution time Memory
466832 2021-08-20T19:29:10 Z TruaShamu Synchronization (JOI13_synchronization) C++17
100 / 100
 359 ms 24260 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
 
int n, m, q;
bool active[100001];
vector<int> graph[100001];
pair<int, int> edges[200001];
 
int info[100001], last_sync[100001];
 
// DFS order
int timer = 1, tin[100001], tout[100001];
// Binary lifting parents
int anc[100001][20];
 
void dfs(int node = 1, int parent = 0) {
    anc[node][0] = parent;
    for (int i = 1; i < 20 && anc[node][i - 1]; i++) {
        anc[node][i] = anc[anc[node][i - 1]][i - 1];
    }
 
    info[node] = 1;
 
    tin[node] = timer++;
    for (int i : graph[node]) if (i != parent) dfs(i, node);
    tout[node] = timer;
}
 
// Fenwick tree
int bit[100001];
 
void update(int pos, int val) { for (; pos <= n; pos += (pos & (-pos))) bit[pos] += val; }
 
int query(int pos) {
    int ans = 0;
    for (; pos; pos -= (pos & (-pos))) ans += bit[pos];
    return ans;
}
 
// Binary lifting
int find_ancestor(int node) {
    int lca = node;
    for (int i = 19; ~i; i--) {
        if (anc[lca][i] && query(tin[anc[lca][i]]) == query(tin[node])) lca = anc[lca][i];
    }
    return lca;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    FOR(i, 1, n) {
        cin >> edges[i].first >> edges[i].second;
        graph[edges[i].first].push_back(edges[i].second);
        graph[edges[i].second].push_back(edges[i].first);
    }
    dfs();
 
    FOR(i, 1, n + 1) {
        update(tin[i], -1);
        update(tout[i], 1);
    }
 
    while (m--) {
        int x;
        cin >> x;
        int u = edges[x].first, v = edges[x].second;
        if (anc[u][0] == v) swap(u, v);
 
        if (active[x]) {
            info[v] = last_sync[v] = info[find_ancestor(u)];
            update(tin[v], -1);
            update(tout[v], 1);
        } else {
            info[find_ancestor(u)] += info[v] - last_sync[v];
            update(tin[v], 1);
            update(tout[v], -1);
        }
        active[x] = !active[x];
    }
 
    while (q--) {
        int x;
        cin >> x;
        cout << info[find_ancestor(x)] << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2680 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 3 ms 2764 KB Output is correct
7 Correct 13 ms 4228 KB Output is correct
8 Correct 13 ms 4296 KB Output is correct
9 Correct 13 ms 4284 KB Output is correct
10 Correct 193 ms 18756 KB Output is correct
11 Correct 194 ms 18756 KB Output is correct
12 Correct 278 ms 23424 KB Output is correct
13 Correct 100 ms 18748 KB Output is correct
14 Correct 122 ms 17856 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 18728 KB Output is correct
2 Correct 96 ms 20596 KB Output is correct
3 Correct 119 ms 22464 KB Output is correct
4 Correct 123 ms 22496 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 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 2 ms 2636 KB Output is correct
6 Correct 3 ms 2892 KB Output is correct
7 Correct 23 ms 4788 KB Output is correct
8 Correct 323 ms 24244 KB Output is correct
9 Correct 359 ms 24192 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 21260 KB Output is correct
2 Correct 204 ms 23592 KB Output is correct
3 Correct 206 ms 23712 KB Output is correct
4 Correct 190 ms 23616 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 17 ms 4300 KB Output is correct
7 Correct 220 ms 19640 KB Output is correct
8 Correct 299 ms 24260 KB Output is correct
9 Correct 111 ms 19772 KB Output is correct
10 Correct 160 ms 19120 KB Output is correct
11 Correct 141 ms 21896 KB Output is correct
12 Correct 132 ms 21828 KB Output is correct
13 Correct 185 ms 23620 KB Output is correct