oj.uz

Submission #231409

# Submission time Handle Problem Language Result Execution time Memory
231409 2020-05-13T14:04:45 Z thebes Synchronization (JOI13_synchronization) C++14
100 / 100
 910 ms 28024 KB 
#include <bits/stdc++.h>
using namespace std;

const int MN = 1e5+5, LG = 19;
int st[3*MN], lz[3*MN], sp[MN][LG], N, M, Q, i, x, y, dep[MN], vis[MN][2], lst[MN], nxt, sz[MN], on[MN];
pair<int,int> e[MN];
vector<int> adj[MN];

inline void upd_lz(int i,int s,int e){
    st[i] += lz[i];
    if(s!=e){
        lz[2*i] += lz[i];
        lz[2*i+1] += lz[i];
    }
    lz[i] = 0;
}

void upd(int i,int s,int e,int ss,int se,int v){
    upd_lz(i, s, e);
    if(s>=ss&&e<=se){lz[i]=v; upd_lz(i,s,e);}
    else{
        if((s+e)/2<ss) upd(2*i+1,(s+e)/2+1,e,ss,se,v),upd_lz(2*i,s,(s+e)/2);
        else if((s+e)/2>=se) upd(2*i,s,(s+e)/2,ss,se,v),upd_lz(2*i+1,(s+e)/2+1,e);
        else upd(2*i,s,(s+e)/2,ss,se,v),upd(2*i+1,(s+e)/2+1,e,ss,se,v);
        st[i]=st[2*i]+st[2*i+1];
    }
}

int qu(int i,int s,int e,int idx){
    upd_lz(i,s,e);
    if(s==e) return st[i];
    else if((s+e)/2<idx) return qu(2*i+1,(s+e)/2+1,e,idx);
    else return qu(2*i,s,(s+e)/2,idx);
}

void dfs(int n,int p,int d){
    vis[n][0] = ++nxt;
    sp[n][0]=p; dep[n]=d;
    for(auto v : adj[n]){
        if(v==p) continue;
        dfs(v,n,d+1);
    }
    vis[n][1] = nxt;
}

int anc(int n){
    int val = qu(1,1,N,vis[n][0]);
    for(int i=LG-1;i>=0;i--){
        if(sp[n][i]){
            int nn = sp[n][i];
            if(qu(1,1,N,vis[nn][0])==val)
                n = nn;
        }
    }
    return n;
}

int main(){
    for(scanf("%d%d%d",&N,&M,&Q),i=1;i<N;i++){
        scanf("%d%d",&x,&y);
        adj[x].push_back(y);
        adj[y].push_back(x);
        e[i]={x,y};
    }
    dfs(1,0,1);
    for(int j=1;j<LG;j++){
        for(i=1;i<=N;i++)
            sp[i][j]=sp[sp[i][j-1]][j-1];
    }
    for(i=1;i<N;i++){
        if(dep[e[i].first]>dep[e[i].second])
            swap(e[i].first,e[i].second);
    }
    for(i=2;i<=N;i++) upd(1,1,N,vis[i][0],vis[i][1],1);
    for(i=1;i<=N;i++) sz[i]=1;
    for(i=1;i<=M;i++){
        scanf("%d",&x);
        int p=e[x].first, c=e[x].second;
        if(on[x]){
            int rt = anc(c);
            lst[x] = sz[c] = sz[rt];
            upd(1,1,N,vis[c][0],vis[c][1],1);
        }
        else{
            upd(1,1,N,vis[c][0],vis[c][1],-1);
            int rt = anc(c);
            sz[rt] += sz[c]-lst[x];
        }
        on[x]=!on[x];
    }
    for(i=1;i<=Q;i++){
        scanf("%d",&x);
        printf("%d\n",sz[anc(x)]);
    }
    return 0;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:78:13: warning: unused variable 'p' [-Wunused-variable]
         int p=e[x].first, c=e[x].second;
             ^
synchronization.cpp:59:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d%d%d",&N,&M,&Q),i=1;i<N;i++){
         ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
synchronization.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~
synchronization.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~
synchronization.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 8 ms 2688 KB Output is correct
7 Correct 33 ms 4480 KB Output is correct
8 Correct 32 ms 4608 KB Output is correct
9 Correct 33 ms 4480 KB Output is correct
10 Correct 423 ms 20984 KB Output is correct
11 Correct 452 ms 20856 KB Output is correct
12 Correct 716 ms 27256 KB Output is correct
13 Correct 257 ms 20720 KB Output is correct
14 Correct 274 ms 19960 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 23544 KB Output is correct
2 Correct 242 ms 23360 KB Output is correct
3 Correct 291 ms 26104 KB Output is correct
4 Correct 276 ms 26104 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 9 ms 2944 KB Output is correct
7 Correct 59 ms 5244 KB Output is correct
8 Correct 853 ms 27896 KB Output is correct
9 Correct 866 ms 27896 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 910 ms 28024 KB Output is correct
2 Correct 450 ms 27128 KB Output is correct
3 Correct 450 ms 27256 KB Output is correct
4 Correct 453 ms 27256 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 8 ms 2816 KB Output is correct
6 Correct 40 ms 4608 KB Output is correct
7 Correct 550 ms 21760 KB Output is correct
8 Correct 880 ms 27896 KB Output is correct
9 Correct 338 ms 21848 KB Output is correct
10 Correct 342 ms 21112 KB Output is correct
11 Correct 371 ms 24696 KB Output is correct
12 Correct 356 ms 24696 KB Output is correct
13 Correct 449 ms 27256 KB Output is correct