oj.uz

Submission #466642

# Submission time Handle Problem Language Result Execution time Memory
466642 2021-08-19T21:35:18 Z TruaShamu Synchronization (JOI13_synchronization) C++17
100 / 100
 386 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 13 ms 4296 KB Output is correct
8 Correct 13 ms 4172 KB Output is correct
9 Correct 13 ms 4224 KB Output is correct
10 Correct 178 ms 18884 KB Output is correct
11 Correct 177 ms 18860 KB Output is correct
12 Correct 234 ms 23428 KB Output is correct
13 Correct 108 ms 18752 KB Output is correct
14 Correct 129 ms 18012 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 20648 KB Output is correct
2 Correct 94 ms 20480 KB Output is correct
3 Correct 116 ms 22516 KB Output is correct
4 Correct 116 ms 22476 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2680 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2720 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 3 ms 2892 KB Output is correct
7 Correct 21 ms 4764 KB Output is correct
8 Correct 300 ms 24120 KB Output is correct
9 Correct 300 ms 24184 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 24132 KB Output is correct
2 Correct 187 ms 23528 KB Output is correct
3 Correct 186 ms 23616 KB Output is correct
4 Correct 188 ms 23624 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 2636 KB Output is correct
4 Correct 2 ms 2680 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 17 ms 4332 KB Output is correct
7 Correct 216 ms 19728 KB Output is correct
8 Correct 386 ms 24260 KB Output is correct
9 Correct 107 ms 19792 KB Output is correct
10 Correct 147 ms 19120 KB Output is correct
11 Correct 152 ms 21844 KB Output is correct
12 Correct 133 ms 21828 KB Output is correct
13 Correct 187 ms 23728 KB Output is correct