oj.uz

Submission #480703

# Submission time Handle Problem Language Result Execution time Memory
480703 2021-10-17T22:33:15 Z SirCovidThe19th Synchronization (JOI13_synchronization) C++17
30 / 100
 526 ms 24568 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[l] -= 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2648 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Incorrect 2 ms 2636 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 158 ms 20580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 6 ms 2764 KB Output is correct
7 Correct 42 ms 4800 KB Output is correct
8 Correct 518 ms 24516 KB Output is correct
9 Correct 526 ms 24568 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 24568 KB Output is correct
2 Correct 387 ms 24196 KB Output is correct
3 Correct 384 ms 24544 KB Output is correct
4 Correct 382 ms 24340 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Incorrect 2 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -