Submission #1298876

#TimeUsernameProblemLanguageResultExecution timeMemory
1298876zhangspicyuwuSynchronization (JOI13_synchronization)C++17
100 / 100
251 ms22308 KiB
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define ll long long
#define i128 __int128
using namespace std;
const int N=1e5+5,mod=1e9+7,imod=(mod+1)/2,inf=1e17;
int n,ans[N],lst[N],m,q,st[N],en[N],idd,spt[17][N],h[N];
pii E[N];
vector<int> adj[N];
bool used[N];
void pre_dfs(int u,int p){
    st[u]=++idd;
    spt[0][u]=p;
    h[u]=h[p]+1;
    for(int j=1;j<17;j++) spt[j][u]=spt[j-1][spt[j-1][u]];
    for(const int v:adj[u]){
        if(v==p) continue;
        pre_dfs(v,u);
    }
    en[u]=idd;
}
int fen[N];
void add(int u,int val){
    while(u<=n){
        fen[u]+=val;
        u+=(u&-u);
    }
}
int get(int u){
    int ans=0;
    while(u){
        ans+=fen[u];
        u-=(u&-u);
    }
    return ans;
}
int Find(int u){
    for(int i=16;i>=0;i--){
        if(get(st[spt[i][u]])==get(st[u])) u=spt[i][u];
    }
    return u;
}
signed main(){
    //freopen("money.in","r",stdin);
    //freopen("money.out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        E[i]={u,v};
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    pre_dfs(1,0);
    for(int i=1;i<n;i++){
        if(h[E[i].fi]<h[E[i].se]) swap(E[i].fi,E[i].se);
    }
    for(int i=1;i<=n;i++) add(st[i],1),add(en[i]+1,-1),ans[i]=1;
    for(int i=1;i<=m;i++){
        int id; cin>>id;
        const auto [u,p]=E[id];
        if(!used[id]){
            ans[Find(p)]+=ans[u]-lst[u];
            add(st[u],-1);
            add(en[u]+1,1);
        }
        else{
            ans[u]=lst[u]=ans[Find(p)];
            add(st[u],1);
            add(en[u]+1,-1);
        }
        used[id]^=1;
    }
    for(int i=1;i<=q;i++){
        int u; cin>>u;
        cout<<ans[Find(u)]<<"\n";
    }
}

Compilation message (stderr)

synchronization.cpp:12:48: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
   12 | const int N=1e5+5,mod=1e9+7,imod=(mod+1)/2,inf=1e17;
      |                                                ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...