oj.uz

Submission #862620

# Submission time Handle Problem Language Result Execution time Memory
862620 2023-10-18T16:09:08 Z Alora Synchronization (JOI13_synchronization) C++17
100 / 100
 219 ms 25168 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 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9816 KB Output is correct
5 Correct 2 ms 9816 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 9 ms 10328 KB Output is correct
8 Correct 9 ms 10332 KB Output is correct
9 Correct 10 ms 10332 KB Output is correct
10 Correct 101 ms 19752 KB Output is correct
11 Correct 102 ms 19536 KB Output is correct
12 Correct 158 ms 24212 KB Output is correct
13 Correct 52 ms 19660 KB Output is correct
14 Correct 94 ms 19112 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 21172 KB Output is correct
2 Correct 59 ms 21840 KB Output is correct
3 Correct 71 ms 23608 KB Output is correct
4 Correct 77 ms 23636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 2 ms 9872 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 19 ms 10944 KB Output is correct
8 Correct 198 ms 24984 KB Output is correct
9 Correct 219 ms 24916 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 23848 KB Output is correct
2 Correct 147 ms 24856 KB Output is correct
3 Correct 115 ms 24912 KB Output is correct
4 Correct 122 ms 25168 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9816 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 11 ms 10332 KB Output is correct
7 Correct 133 ms 20564 KB Output is correct
8 Correct 204 ms 25128 KB Output is correct
9 Correct 71 ms 20700 KB Output is correct
10 Correct 98 ms 20272 KB Output is correct
11 Correct 83 ms 23124 KB Output is correct
12 Correct 83 ms 23120 KB Output is correct
13 Correct 121 ms 24808 KB Output is correct