oj.uz

Submission #274226

# Submission time Handle Problem Language Result Execution time Memory
274226 2020-08-19T10:07:02 Z LifeHappen__ Synchronization (JOI13_synchronization) C++14
100 / 100
 437 ms 38820 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(v,a) for(auto &v:a)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(a) begin(a),end(a)

const int N=2e5+5;
int n,m,q,st[N],en[N],id;
vector<int> ad[N];
ii edge[N];
int pd[N][21],it[N],act[N],a[N],last[N];

void dfs(int u,int par){
    forinc(i,1,20) pd[u][i]=pd[pd[u][i-1]][i-1];
    st[u]=++id;
    a[u]=1;
    forv(v,ad[u]) if(v!=par){
        pd[v][0]=u;
        dfs(v,u);
    }
    en[u]=id;
}
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 l,int r,int val){
        //cerr<<l<<' '<<r+1<<'\n';
    upd(l,val);
    upd(r+1, -val);
}
int root(int x){
    fordec(i,20,0) if(pd[x][i]!=0 && get(st[pd[x][i]])==get(st[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){
        cin>>edge[i].fi>>edge[i].se;
        ad[edge[i].fi].pb(edge[i].se);
        ad[edge[i].se].pb(edge[i].fi);
    }
    dfs(1,0);
    //forinc(i,1,n) cout<<st[i]<<'\n';
    forinc(i,1,n) up(st[i],en[i],1);
    while(m--){
        int now;
        cin>>now;
        int u,v;
        tie(u,v)=edge[now];
        //cerr<<u<<' '<<v<<'\n';
        if(pd[u][0]==v) swap(u,v);
        if(act[now]){
            a[v]=last[v]=a[root(u)];
            up(st[v],en[v],1);
        } else{
            a[root(u)]+=a[v]-last[v];
            up(st[v],en[v],-1);
        }
        act[now]=!act[now];
    }
    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 4 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 6 ms 5376 KB Output is correct
7 Correct 19 ms 7936 KB Output is correct
8 Correct 17 ms 7936 KB Output is correct
9 Correct 17 ms 7936 KB Output is correct
10 Correct 282 ms 33876 KB Output is correct
11 Correct 300 ms 33784 KB Output is correct
12 Correct 337 ms 38008 KB Output is correct
13 Correct 129 ms 33644 KB Output is correct
14 Correct 207 ms 32536 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 35036 KB Output is correct
2 Correct 109 ms 34676 KB Output is correct
3 Correct 167 ms 36600 KB Output is correct
4 Correct 177 ms 36600 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 7 ms 5380 KB Output is correct
7 Correct 30 ms 8448 KB Output is correct
8 Correct 406 ms 38820 KB Output is correct
9 Correct 420 ms 38776 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 38776 KB Output is correct
2 Correct 236 ms 37668 KB Output is correct
3 Correct 211 ms 37744 KB Output is correct
4 Correct 220 ms 37816 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5024 KB Output is correct
2 Correct 4 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 6 ms 5376 KB Output is correct
6 Correct 24 ms 8064 KB Output is correct
7 Correct 337 ms 34680 KB Output is correct
8 Correct 437 ms 38776 KB Output is correct
9 Correct 172 ms 34712 KB Output is correct
10 Correct 229 ms 33820 KB Output is correct
11 Correct 167 ms 36340 KB Output is correct
12 Correct 165 ms 36268 KB Output is correct
13 Correct 218 ms 37752 KB Output is correct