Submission #1114844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114844		Newtonabc	Synchronization (JOI13_synchronization)	C++14	100 / 100	430 ms	25164 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40