oj.uz

Submission #274765

# Submission time Handle Problem Language Result Execution time Memory
274765 2020-08-19T15:21:58 Z LifeHappen__ Synchronization (JOI13_synchronization) C++14
100 / 100
 423 ms 40312 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define forinc(a,b,c) for(int a=b, _c=c; a<=_c; ++a)
#define fordec(a,b,c) for(int a=b, _c=c; a>=_c; --a)
#define forv(a,b) for(auto &a:b)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(a) begin(a),end(a)
#define rall(a) rbegin(a),rend(a)

const int N=2e5+5;
int n,m,q;
ii edge[N];
vector<int> ad[N];
int tin[N],tout[N],id,it[N],a[N],last[N],dd[N];
int pd[N][23];

void upd(int i,int val){
    for(; i<=n; i+=i&-i) it[i]+=val;
}
int get(int i){
    int ans=0;
    for(; i; i-=i&-i) ans+=it[i];
    return ans;
}
void up(int u,int v,int val){
    upd(u,val); upd(v+1,-val);
}

void dfs(int u,int par=-1){
    tin[u]=++id;
    forinc(i,1,22) pd[u][i]=pd[pd[u][i-1]][i-1];
    a[u]=1;
    forv(v,ad[u]) if(v!=par){
        pd[v][0]=u;
        dfs(v,u);
    }
    tout[u]=id;
}
int root(int x){
    fordec(i,22,0) if(pd[x][i] && get(tin[pd[x][i]])==get(tin[x])) x=pd[x][i];
    return x;
}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>q;
    forinc(i,1,n-1){
        int u,v;
        cin>>u>>v;
        ad[u].pb(v); ad[v].pb(u);
        edge[i]={u,v};
    }
    dfs(1,0);
    forinc(i,1,n) up(tin[i],tout[i],1);
    while(m--){
        int x;
        cin>>x;
        int u,v; tie(u,v)=edge[x];
        if(pd[u][0]==v) swap(u,v);
        if(!dd[x]){
            a[root(u)]+=a[v]-last[v];
            up(tin[v],tout[v],-1);
        }else{
            a[v]=last[v]=a[root(u)];
            up(tin[v],tout[v],1);
        }
        dd[x]=!dd[x];
    }
    while(q--){
        int x;
        cin>>x;
        cout<<a[root(x)]<<'\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 5 ms 5376 KB Output is correct
7 Correct 17 ms 8064 KB Output is correct
8 Correct 17 ms 8064 KB Output is correct
9 Correct 17 ms 8064 KB Output is correct
10 Correct 259 ms 35448 KB Output is correct
11 Correct 255 ms 35320 KB Output is correct
12 Correct 309 ms 39548 KB Output is correct
13 Correct 110 ms 35180 KB Output is correct
14 Correct 182 ms 34040 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 34676 KB Output is correct
2 Correct 116 ms 34164 KB Output is correct
3 Correct 139 ms 36472 KB Output is correct
4 Correct 140 ms 36476 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 5 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 5 ms 5376 KB Output is correct
7 Correct 24 ms 8320 KB Output is correct
8 Correct 423 ms 37416 KB Output is correct
9 Correct 381 ms 37368 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 37344 KB Output is correct
2 Correct 223 ms 36856 KB Output is correct
3 Correct 215 ms 37196 KB Output is correct
4 Correct 219 ms 37112 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 5 ms 5376 KB Output is correct
6 Correct 22 ms 8192 KB Output is correct
7 Correct 330 ms 36344 KB Output is correct
8 Correct 372 ms 40312 KB Output is correct
9 Correct 137 ms 36332 KB Output is correct
10 Correct 223 ms 35296 KB Output is correct
11 Correct 145 ms 37748 KB Output is correct
12 Correct 171 ms 37748 KB Output is correct
13 Correct 222 ms 39548 KB Output is correct