oj.uz

Submission #968281

# Submission time Handle Problem Language Result Execution time Memory
968281 2024-04-23T09:28:25 Z Beerus13 Synchronization (JOI13_synchronization) C++14
100 / 100
 203 ms 30128 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
const int N = 2e5 + 5;
const int K = 18;

int n, m, q, numDFS;
int P[N][K], in[N], out[N], bit[N], last_val[N], res[N];
pii edge[N];
bool vs[N];
vector<int> g[N];

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

void update(int l, int r, int val) {
    update(l, val);
    update(r + 1, -val);
}

int get(int i) {
    int res = 0;
    for(; i; i -= i & -i) res += bit[i];
    return res;
}

int find(int u) {
    for(int i = K - 1; i >= 0; --i) {
        // check xem co cung tplt ko
        if(get(in[u]) == get(in[P[u][i]])) {
            u = P[u][i];
        }
    }
    return u;
}

void dfs(int u, int p = 0) {
    in[u] = ++numDFS;
    P[u][0] = p;
    for(int i = 1; i < K; ++i) P[u][i] = P[P[u][i - 1]][i - 1];
    for(int v : g[u]) if(v != p) {
        dfs(v, u);
    }
    out[u] = numDFS;
}

void solve() {
    cin >> n >> m >> q;
    for(int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        edge[i] = make_pair(u, v);
    }
    dfs(1);
    for(int i = 1; i <= n; ++i) {
        res[i] = 1;
        update(in[i], out[i], 1);
    }
    for(int i = 1, pos; i <= m; ++i) {
        cin >> pos;
        auto [u, v] = edge[pos];
        if(in[u] > in[v]) swap(u, v);
        if(!vs[pos]) {
            int rt = find(u);
            // join (rt, v) : rt = root(u), v = root(v)
            int nw = res[rt] + res[v] - last_val[pos];
            res[rt] = nw;
            update(in[v], out[v], -1);
        } else {
            res[v] = last_val[pos] = res[find(u)];
            update(in[v], out[v], 1);
        }
        vs[pos] ^= 1;
    }
    while(q--) {
        int u; cin >> u;
        cout << res[find(u)] << '\n';
    }
}


signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    return 0;
}

Compilation message

synchronization.cpp: In function 'void solve()':
synchronization.cpp:64:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |         auto [u, v] = edge[pos];
      |              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 12 ms 13404 KB Output is correct
8 Correct 12 ms 13400 KB Output is correct
9 Correct 12 ms 13464 KB Output is correct
10 Correct 135 ms 24628 KB Output is correct
11 Correct 143 ms 24480 KB Output is correct
12 Correct 151 ms 29012 KB Output is correct
13 Correct 63 ms 24404 KB Output is correct
14 Correct 89 ms 23972 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 26732 KB Output is correct
2 Correct 78 ms 26824 KB Output is correct
3 Correct 73 ms 28500 KB Output is correct
4 Correct 72 ms 28584 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 3 ms 13144 KB Output is correct
7 Correct 15 ms 13912 KB Output is correct
8 Correct 196 ms 29836 KB Output is correct
9 Correct 193 ms 29968 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 29836 KB Output is correct
2 Correct 116 ms 29572 KB Output is correct
3 Correct 136 ms 29776 KB Output is correct
4 Correct 117 ms 29780 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 17 ms 13524 KB Output is correct
7 Correct 169 ms 25420 KB Output is correct
8 Correct 203 ms 30128 KB Output is correct
9 Correct 93 ms 25428 KB Output is correct
10 Correct 118 ms 25424 KB Output is correct
11 Correct 101 ms 27836 KB Output is correct
12 Correct 107 ms 27964 KB Output is correct
13 Correct 114 ms 29820 KB Output is correct