oj.uz

Submission #862622

# Submission time Handle Problem Language Result Execution time Memory
862622 2023-10-18T16:10:12 Z Alora Synchronization (JOI13_synchronization) C++17
100 / 100
 190 ms 24080 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 {
          	int x = find_ancestor(u);
            info[x] += info[v] - last_sync[v];
          	info[v] = info[x]; 
            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 9880 KB Output is correct
3 Correct 2 ms 10072 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 10 ms 10332 KB Output is correct
8 Correct 9 ms 10332 KB Output is correct
9 Correct 9 ms 10392 KB Output is correct
10 Correct 93 ms 18648 KB Output is correct
11 Correct 96 ms 18516 KB Output is correct
12 Correct 146 ms 23124 KB Output is correct
13 Correct 51 ms 18900 KB Output is correct
14 Correct 64 ms 18264 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 21020 KB Output is correct
2 Correct 56 ms 21012 KB Output is correct
3 Correct 74 ms 22868 KB Output is correct
4 Correct 74 ms 23276 KB Output is correct

Subtask #3
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 10072 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 9884 KB Output is correct
7 Correct 14 ms 10844 KB Output is correct
8 Correct 180 ms 23832 KB Output is correct
9 Correct 190 ms 24080 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 23892 KB Output is correct
2 Correct 115 ms 23636 KB Output is correct
3 Correct 125 ms 23936 KB Output is correct
4 Correct 115 ms 24016 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9872 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9656 KB Output is correct
5 Correct 3 ms 9904 KB Output is correct
6 Correct 12 ms 10512 KB Output is correct
7 Correct 133 ms 19416 KB Output is correct
8 Correct 181 ms 23932 KB Output is correct
9 Correct 60 ms 19656 KB Output is correct
10 Correct 84 ms 19280 KB Output is correct
11 Correct 90 ms 22056 KB Output is correct
12 Correct 78 ms 21844 KB Output is correct
13 Correct 113 ms 23784 KB Output is correct