oj.uz

Submission #874229

# Submission time Handle Problem Language Result Execution time Memory
874229 2023-11-16T13:10:37 Z justinlgl20 Synchronization (JOI13_synchronization) C++14
100 / 100
 1131 ms 27080 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define f first
#define s second

vector<int> adj[100005];

int n, m, q;
pii edges[200005];
int dat[100005];

int cnt;
int tin[100005];
int tout[100005];
int hop[100001][20];

void dfs(int u, int p) {
    hop[u][0] = p;
    for (int i = 1; i < 20 and hop[u][i-1]; i++) {
        hop[u][i] = hop[hop[u][i-1]][i-1];
    }
    dat[u] = 1;
    tin[u] = ++cnt;
    for (int i : adj[u]) {
        if (i != p) dfs(i, u);
    }
    tout[u] = cnt+1;
}



int last[100005];

int bit[100005];

void upd(int pos, int val) { for (; pos <= n; pos += (pos & (-pos))) bit[pos] += val; }

int query(int p) {
    int ans = 0;
    for (; p; p -= (p & (-p))) ans += bit[p];
    return ans;
}
int anc(int u) {
    int g = u;
    for (int i = 19; ~i; i--) {
        if (hop[g][i] and query(tin[hop[g][i]]) == query(tin[u])) g = hop[g][i];
    }
    return g;
}

int alive[100005];

int main() {
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        cin >> edges[i].f >> edges[i].s;
        adj[edges[i].f].push_back(edges[i].s);
        adj[edges[i].s].push_back(edges[i].f);
    }
    dfs(1, 0);

    cerr << "DBG\n";
    for (int i = 1; i < n+1; i++) {
        upd(tin[i], -1);
        upd(tout[i], 1);
    }
    cerr << "SUCCESS\n";
    while (m--) {
        int x; cin >> x;
        int u = edges[x].f;
        int v = edges[x].s;
        if (hop[u][0] == v) swap(u, v);
        
        if (alive[x]) {
            dat[v] = last[v] = dat[anc(u)];
            cerr << anc(u) << " " << last[v] << "\n";
            upd(tin[v], -1);
            upd(tout[v], 1);
        }
        else {
            dat[anc(u)] += dat[v]-last[v];
            cerr << anc(u) << "\n";
            upd(tin[v], 1);
            upd(tout[v], -1);
        }
        alive[x] = not alive[x];
    }
    while (q--) {
        int x; cin >> x;
        cout << dat[anc(x)] << "\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 2 ms 8024 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8024 KB Output is correct
6 Correct 9 ms 8028 KB Output is correct
7 Correct 84 ms 8840 KB Output is correct
8 Correct 81 ms 8788 KB Output is correct
9 Correct 76 ms 8792 KB Output is correct
10 Correct 810 ms 21396 KB Output is correct
11 Correct 881 ms 21328 KB Output is correct
12 Correct 946 ms 25904 KB Output is correct
13 Correct 724 ms 20684 KB Output is correct
14 Correct 366 ms 20316 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 722 ms 23076 KB Output is correct
2 Correct 677 ms 22784 KB Output is correct
3 Correct 408 ms 24624 KB Output is correct
4 Correct 398 ms 24400 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8192 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 3 ms 8028 KB Output is correct
5 Correct 2 ms 8188 KB Output is correct
6 Correct 11 ms 8280 KB Output is correct
7 Correct 97 ms 9300 KB Output is correct
8 Correct 1119 ms 26868 KB Output is correct
9 Correct 1131 ms 26756 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1116 ms 26772 KB Output is correct
2 Correct 592 ms 25684 KB Output is correct
3 Correct 559 ms 25908 KB Output is correct
4 Correct 557 ms 25636 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 2 ms 8188 KB Output is correct
3 Correct 2 ms 8024 KB Output is correct
4 Correct 3 ms 8196 KB Output is correct
5 Correct 13 ms 8028 KB Output is correct
6 Correct 91 ms 8856 KB Output is correct
7 Correct 987 ms 22412 KB Output is correct
8 Correct 1115 ms 27080 KB Output is correct
9 Correct 840 ms 22280 KB Output is correct
10 Correct 514 ms 21332 KB Output is correct
11 Correct 838 ms 24148 KB Output is correct
12 Correct 850 ms 23888 KB Output is correct
13 Correct 560 ms 25732 KB Output is correct