oj.uz

Submission #467881

# Submission time Handle Problem Language Result Execution time Memory
467881 2021-08-25T10:40:16 Z ommivorous Synchronization (JOI13_synchronization) C++14
100 / 100
 325 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 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 2676 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 14 ms 4228 KB Output is correct
8 Correct 14 ms 4284 KB Output is correct
9 Correct 16 ms 4292 KB Output is correct
10 Correct 189 ms 18756 KB Output is correct
11 Correct 182 ms 18848 KB Output is correct
12 Correct 257 ms 23364 KB Output is correct
13 Correct 92 ms 18736 KB Output is correct
14 Correct 133 ms 17808 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 20728 KB Output is correct
2 Correct 95 ms 20420 KB Output is correct
3 Correct 121 ms 22596 KB Output is correct
4 Correct 119 ms 22444 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 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 2672 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 3 ms 2856 KB Output is correct
7 Correct 21 ms 4792 KB Output is correct
8 Correct 325 ms 24200 KB Output is correct
9 Correct 316 ms 24196 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 24172 KB Output is correct
2 Correct 189 ms 23544 KB Output is correct
3 Correct 191 ms 23628 KB Output is correct
4 Correct 191 ms 23652 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 2680 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2824 KB Output is correct
6 Correct 17 ms 4352 KB Output is correct
7 Correct 256 ms 19632 KB Output is correct
8 Correct 310 ms 24260 KB Output is correct
9 Correct 104 ms 19816 KB Output is correct
10 Correct 148 ms 19136 KB Output is correct
11 Correct 143 ms 21968 KB Output is correct
12 Correct 149 ms 21956 KB Output is correct
13 Correct 190 ms 23716 KB Output is correct