oj.uz

Submission #1081000

# Submission time Handle Problem Language Result Execution time Memory
1081000 2024-08-29T16:50:24 Z hahahaha Synchronization (JOI13_synchronization) C++17
100 / 100
 213 ms 24336 KB 
/*
JOI 2013 Synchronisation
*/
 
#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 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 9 ms 4404 KB Output is correct
8 Correct 8 ms 4184 KB Output is correct
9 Correct 8 ms 4232 KB Output is correct
10 Correct 100 ms 18992 KB Output is correct
11 Correct 119 ms 18768 KB Output is correct
12 Correct 167 ms 23568 KB Output is correct
13 Correct 49 ms 18796 KB Output is correct
14 Correct 69 ms 18004 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 20816 KB Output is correct
2 Correct 55 ms 20564 KB Output is correct
3 Correct 71 ms 22520 KB Output is correct
4 Correct 69 ms 22612 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 2 ms 2904 KB Output is correct
7 Correct 13 ms 4956 KB Output is correct
8 Correct 200 ms 24336 KB Output is correct
9 Correct 195 ms 24208 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 24280 KB Output is correct
2 Correct 109 ms 23888 KB Output is correct
3 Correct 104 ms 23700 KB Output is correct
4 Correct 104 ms 23748 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2820 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 11 ms 4384 KB Output is correct
7 Correct 143 ms 19788 KB Output is correct
8 Correct 205 ms 24148 KB Output is correct
9 Correct 78 ms 20132 KB Output is correct
10 Correct 89 ms 19116 KB Output is correct
11 Correct 76 ms 22020 KB Output is correct
12 Correct 76 ms 21840 KB Output is correct
13 Correct 111 ms 23892 KB Output is correct