oj.uz

Submission #618144

# Submission time Handle Problem Language Result Execution time Memory
618144 2022-08-02T00:40:14 Z czhang2718 Synchronization (JOI13_synchronization) C++17
100 / 100
 276 ms 27468 KB 
#include "bits/stdc++.h"
using namespace std;

const int N=1e5+1, K=18;
int n, m, q, t;
vector<int> adj[N];
int par[N][K];
int h[N];
int tin[N], tout[N];
int a[N], b[N];
int edge[N][2];
bool on[N];

void dfs(int x){
    tin[x]=++t;
    for(int i=1; i<K; i++){
        par[x][i]=par[par[x][i-1]][i-1];
    }
    for(int k:adj[x]){
        if(k==par[x][0]) continue;
        par[k][0]=x;
        h[k]=h[x]+1;
        dfs(k);
    }
    tout[x]=++t;
}

int sum[2*N];

int qry(int i){
    int ret=0;
    while(i){
        ret+=sum[i];
        i-=i&-i;
    }
    return ret;
}

void upd(int i, int v){
    while(i<=2*n){
        sum[i]+=v;
        i+=i&-i;
    }
}

void upd(int l, int r, int v){
    upd(l, v);
    upd(r+1, -v);
}

int getrt(int x){
    int u=x;
    int c=qry(tin[x]);
    for(int k=K-1; k>=0; k--){
        if(par[u][k] && c-qry(tin[par[u][k]])==h[x]-h[par[u][k]]) u=par[u][k]; 
    }
    return u;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m >> q;
    for(int i=1; i<n; i++){
        int u,v; cin >> u >> v;
        edge[i][0]=u;
        edge[i][1]=v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);

    for(int i=1; i<=n; i++) a[i]=1;

    while(m--){
        int e; cin >> e;
        int u=edge[e][0], v=edge[e][1];
        if(h[u]>h[v]) swap(u,v);
        // u
        // v
        int rt=getrt(u);
        // cout << "uvroot " << u << " " << v << " " << rt << "\n";
        if(on[e]){
            b[e]=a[rt];
            a[v]=a[rt];
            upd(tin[v], tout[v], -1);
        }
        else{
            a[rt]=a[rt]+a[v]-b[e];
            upd(tin[v], tout[v], 1);
        }
        // cout << "a[" << rt << "] = " << a[rt] << "\n";
        on[e]=!on[e];
    }

    while(q--){
        int u; cin >> u;
        cout << a[getrt(u)] << "\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2680 KB Output is correct
3 Correct 2 ms 2680 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 10 ms 4240 KB Output is correct
8 Correct 14 ms 4248 KB Output is correct
9 Correct 13 ms 4180 KB Output is correct
10 Correct 150 ms 18872 KB Output is correct
11 Correct 158 ms 18932 KB Output is correct
12 Correct 215 ms 26568 KB Output is correct
13 Correct 72 ms 18760 KB Output is correct
14 Correct 105 ms 17900 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 22232 KB Output is correct
2 Correct 72 ms 22080 KB Output is correct
3 Correct 94 ms 25680 KB Output is correct
4 Correct 94 ms 25596 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2660 KB Output is correct
6 Correct 3 ms 2912 KB Output is correct
7 Correct 17 ms 5108 KB Output is correct
8 Correct 276 ms 27412 KB Output is correct
9 Correct 248 ms 27376 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 27468 KB Output is correct
2 Correct 144 ms 26612 KB Output is correct
3 Correct 135 ms 26860 KB Output is correct
4 Correct 157 ms 26836 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2820 KB Output is correct
6 Correct 17 ms 4308 KB Output is correct
7 Correct 192 ms 19640 KB Output is correct
8 Correct 260 ms 27456 KB Output is correct
9 Correct 95 ms 19904 KB Output is correct
10 Correct 130 ms 19100 KB Output is correct
11 Correct 101 ms 23420 KB Output is correct
12 Correct 99 ms 23424 KB Output is correct
13 Correct 147 ms 26840 KB Output is correct