oj.uz

Submission #832924

# Submission time Handle Problem Language Result Execution time Memory
832924 2023-08-21T16:44:09 Z epicci23 Synchronization (JOI13_synchronization) C++17
100 / 100
 241 ms 24236 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 2632 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2692 KB Output is correct
6 Correct 2 ms 2824 KB Output is correct
7 Correct 9 ms 4180 KB Output is correct
8 Correct 11 ms 4296 KB Output is correct
9 Correct 9 ms 4180 KB Output is correct
10 Correct 154 ms 18864 KB Output is correct
11 Correct 138 ms 18868 KB Output is correct
12 Correct 173 ms 23428 KB Output is correct
13 Correct 51 ms 18748 KB Output is correct
14 Correct 77 ms 17860 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 20644 KB Output is correct
2 Correct 71 ms 20528 KB Output is correct
3 Correct 82 ms 22500 KB Output is correct
4 Correct 76 ms 22540 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2688 KB Output is correct
6 Correct 3 ms 2916 KB Output is correct
7 Correct 16 ms 4796 KB Output is correct
8 Correct 216 ms 24204 KB Output is correct
9 Correct 241 ms 24236 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 24180 KB Output is correct
2 Correct 120 ms 23612 KB Output is correct
3 Correct 118 ms 23664 KB Output is correct
4 Correct 120 ms 23760 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2684 KB Output is correct
3 Correct 1 ms 2684 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2828 KB Output is correct
6 Correct 12 ms 4344 KB Output is correct
7 Correct 176 ms 19620 KB Output is correct
8 Correct 200 ms 24204 KB Output is correct
9 Correct 75 ms 19800 KB Output is correct
10 Correct 123 ms 19152 KB Output is correct
11 Correct 83 ms 21916 KB Output is correct
12 Correct 93 ms 21908 KB Output is correct
13 Correct 138 ms 23704 KB Output is correct