oj.uz

Submission #480705

# Submission time Handle Problem Language Result Execution time Memory
480705 2021-10-17T22:48:24 Z SirCovidThe19th Synchronization (JOI13_synchronization) C++17
100 / 100
 620 ms 24572 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int mx = 1e5 + 5, ml = 17;
 
int n, m, q, vals[mx], ans[mx], bit[mx], up[mx][ml], tin[mx], tout[mx], ti; 
 
bool on[mx]; vector<int> adj[mx]; vector<pair<int, int>> edg;
 
void dfs(int u){
    tin[u] = ++ti;
    for (int l = 1; l < ml; l++) up[u][l] = up[up[u][l - 1]][l - 1];
    for (int v : adj[u]) if (v != up[u][0]) up[v][0] = u, dfs(v);
    tout[u] = ti;
}
void upd(int l, int r, int v){
    for (; l <= n; l += l & (-l)) bit[l] += v;
    for (r++; r <= n; r += r & (-r)) bit[r] -= v;
}
int qry(int i){
    int ret = 0;
	for(;i; i -= i & (-i)) ret += bit[i];
	return ret;
}
int par(int i){
    for (int l = ml - 1; ~l; l--){
        int anc = up[i][l];
        if (anc and qry(tin[i]) == qry(tin[anc])) i = anc;
    }
    return i;
}
 
int main(){
    cin >> n >> m >> q; edg.resize(n);
    for (int i = 1; i < n; i++){
        int a, b; cin >> a >> b; 
        adj[a].push_back(b); adj[b].push_back(a);
        edg[i] = {a, b};
    }
 
    dfs(1);
    for (int i = 1; i <= n; i++) vals[i] = ans[i] = 1, upd(tin[i], tout[i], 1);
 
    while (m--){
        int op, u, v; cin >> op; u = edg[op].first, v = edg[op].second; 
        if (u != up[v][0]) swap(u, v); //u up, v down
      
        if (!on[op]){
            u = par(u); 
            vals[u] += vals[v]; ans[u] += vals[v];
            vals[v] = 0; ans[v] = 0;
            upd(tin[v], tout[v], -1);
        }
        else{
            ans[v] = ans[par(u)];
            upd(tin[v], tout[v], 1); 
        }
        on[op] = !on[op];
    }
    while (q--){
        int ask; cin >> ask;
        cout<<ans[par(ask)]<<endl;
    }
}

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 2648 KB Output is correct
6 Correct 3 ms 2788 KB Output is correct
7 Correct 20 ms 4044 KB Output is correct
8 Correct 20 ms 4136 KB Output is correct
9 Correct 20 ms 4044 KB Output is correct
10 Correct 299 ms 17628 KB Output is correct
11 Correct 268 ms 17604 KB Output is correct
12 Correct 316 ms 23800 KB Output is correct
13 Correct 162 ms 17484 KB Output is correct
14 Correct 190 ms 17096 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 18584 KB Output is correct
2 Correct 153 ms 20412 KB Output is correct
3 Correct 172 ms 23196 KB Output is correct
4 Correct 194 ms 23136 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 2636 KB Output is correct
6 Correct 5 ms 2764 KB Output is correct
7 Correct 39 ms 4564 KB Output is correct
8 Correct 533 ms 21716 KB Output is correct
9 Correct 504 ms 21964 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 21736 KB Output is correct
2 Correct 387 ms 21920 KB Output is correct
3 Correct 431 ms 22044 KB Output is correct
4 Correct 383 ms 22084 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 2636 KB Output is correct
5 Correct 5 ms 2764 KB Output is correct
6 Correct 41 ms 4300 KB Output is correct
7 Correct 487 ms 18508 KB Output is correct
8 Correct 571 ms 24572 KB Output is correct
9 Correct 350 ms 18644 KB Output is correct
10 Correct 375 ms 18368 KB Output is correct
11 Correct 351 ms 21704 KB Output is correct
12 Correct 399 ms 21848 KB Output is correct
13 Correct 373 ms 24364 KB Output is correct