oj.uz

Submission #1114844

# Submission time Handle Problem Language Result Execution time Memory
1114844 2024-11-19T17:01:48 Z Newtonabc Synchronization (JOI13_synchronization) C++14
100 / 100
 430 ms 25164 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int MIDX=1e5+5;
vector<int> adj[N];
pair<int,int> edge[N];
int dp[2][N],pa[18][N],in[N],out[N],cnt=1,fw[N];
bool op[N];
void upd(int idx,int val){while(idx<=MIDX){fw[idx]+=val; idx+=idx & -idx;}}
int read(int idx){int sum=0; while(idx>0){sum+=fw[idx]; idx-=idx & -idx;} return sum;}
void dfs(int u,int p){
    pa[0][u]=p;
    in[u]=cnt++;
    for(int i=0;i<adj[u].size();i++){
        int v=adj[u][i];
        if(v==p) continue;
        dfs(v,u);
    }
    out[u]=cnt;
}
int findr(int u){
    for(int i=17;i>=0;i--) if(read(in[pa[i][u]])==read(in[u])) u=pa[i][u];
    return u;
}
int main(){
    int n,m,q;
    cin>>n >>m >>q;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a >>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        edge[i].first=a,edge[i].second=b;
    }
    dfs(1,1);
    for(int i=1;i<=n;i++) dp[0][i]=1,upd(in[i],1),upd(out[i],-1);
    for(int i=1;i<=17;i++) for(int j=1;j<=n;j++) pa[i][j]=pa[i-1][pa[i-1][j]];
    for(int i=0;i<m;i++){
        int u,tmpc,tmpp;
        cin>>u;
        op[u]^=1;
        tmpc=edge[u].first,tmpp=edge[u].second;
        if(pa[0][edge[u].first]!=edge[u].second) swap(tmpc,tmpp);\
        if(op[u]){
            upd(in[tmpc],-1),upd(out[tmpc],1);
            tmpp=findr(tmpp);
            dp[0][tmpp]+=dp[0][tmpc]-dp[1][tmpc];
        }
        else{
            tmpp=findr(tmpc);
            upd(in[tmpc],1),upd(out[tmpc],-1);
            dp[0][tmpc]=dp[1][tmpc]=dp[0][tmpp];
        }
        /*for(int i=1;i<=n;i++) cout<<dp[0][i] <<" ";
        cout<<"\n";
        for(int i=1;i<=n;i++) cout<<dp[1][i] <<" ";
        cout<<"\n\n";*/
    }
    for(int i=0;i<q;i++){
        int inp;
        cin>>inp;
        cout<<dp[0][findr(inp)] <<"\n";
    }

}

Compilation message

synchronization.cpp: In function 'void dfs(int, int)':
synchronization.cpp:14:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i=0;i<adj[u].size();i++){
      |                 ~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12368 KB Output is correct
2 Correct 3 ms 12476 KB Output is correct
3 Correct 4 ms 12368 KB Output is correct
4 Correct 4 ms 12368 KB Output is correct
5 Correct 3 ms 12368 KB Output is correct
6 Correct 4 ms 12368 KB Output is correct
7 Correct 17 ms 13052 KB Output is correct
8 Correct 17 ms 12880 KB Output is correct
9 Correct 16 ms 13000 KB Output is correct
10 Correct 190 ms 17968 KB Output is correct
11 Correct 188 ms 17992 KB Output is correct
12 Correct 255 ms 24136 KB Output is correct
13 Correct 111 ms 18112 KB Output is correct
14 Correct 122 ms 17480 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 21064 KB Output is correct
2 Correct 128 ms 20808 KB Output is correct
3 Correct 108 ms 23624 KB Output is correct
4 Correct 114 ms 23596 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12368 KB Output is correct
2 Correct 3 ms 12536 KB Output is correct
3 Correct 3 ms 12368 KB Output is correct
4 Correct 3 ms 12368 KB Output is correct
5 Correct 3 ms 12368 KB Output is correct
6 Correct 6 ms 12624 KB Output is correct
7 Correct 43 ms 13732 KB Output is correct
8 Correct 396 ms 24904 KB Output is correct
9 Correct 430 ms 25164 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 24904 KB Output is correct
2 Correct 302 ms 25004 KB Output is correct
3 Correct 329 ms 25160 KB Output is correct
4 Correct 324 ms 24868 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12368 KB Output is correct
2 Correct 3 ms 12368 KB Output is correct
3 Correct 3 ms 12368 KB Output is correct
4 Correct 3 ms 12368 KB Output is correct
5 Correct 6 ms 12368 KB Output is correct
6 Correct 36 ms 13136 KB Output is correct
7 Correct 401 ms 19064 KB Output is correct
8 Correct 388 ms 24904 KB Output is correct
9 Correct 302 ms 19116 KB Output is correct
10 Correct 315 ms 18848 KB Output is correct
11 Correct 292 ms 22108 KB Output is correct
12 Correct 293 ms 22088 KB Output is correct
13 Correct 324 ms 24904 KB Output is correct