oj.uz

Submission #470475

# Submission time Handle Problem Language Result Execution time Memory
470475 2021-09-04T02:56:18 Z hellowsdf Synchronization (JOI13_synchronization) C++14
100 / 100
 318 ms 21736 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];

int timer = 1, tin[100001], tout[100001];
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;
}

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;
}

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 2636 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 13 ms 4224 KB Output is correct
8 Correct 13 ms 4288 KB Output is correct
9 Correct 13 ms 4228 KB Output is correct
10 Correct 184 ms 17108 KB Output is correct
11 Correct 190 ms 16836 KB Output is correct
12 Correct 237 ms 21448 KB Output is correct
13 Correct 78 ms 17084 KB Output is correct
14 Correct 128 ms 16528 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 19024 KB Output is correct
2 Correct 97 ms 18884 KB Output is correct
3 Correct 119 ms 21188 KB Output is correct
4 Correct 119 ms 21136 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 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 2672 KB Output is correct
6 Correct 3 ms 2892 KB Output is correct
7 Correct 21 ms 4776 KB Output is correct
8 Correct 318 ms 21700 KB Output is correct
9 Correct 306 ms 21700 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 21692 KB Output is correct
2 Correct 188 ms 21632 KB Output is correct
3 Correct 191 ms 21696 KB Output is correct
4 Correct 187 ms 21700 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 2764 KB Output is correct
6 Correct 18 ms 4300 KB Output is correct
7 Correct 223 ms 17192 KB Output is correct
8 Correct 309 ms 21736 KB Output is correct
9 Correct 100 ms 17732 KB Output is correct
10 Correct 161 ms 17220 KB Output is correct
11 Correct 133 ms 19660 KB Output is correct
12 Correct 135 ms 19728 KB Output is correct
13 Correct 190 ms 21668 KB Output is correct