Submission #769852

#	Time	Username	Problem	Language	Result	Execution time	Memory
769852		Essa2006	Synchronization (JOI13_synchronization)	C++14	100 / 100	463 ms	95068 KiB

synchronization

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int inf=1e9, lg=20;
int n, q1, q2, m, time_;
vector<int>C, Dt, Ft, Bit, R;
vector<vector<int>>A, Lca;
map<int, pair<int, int>>mp;
 
void pre(){
    C.clear(), Dt.clear(), Ft.clear(), Bit.clear(), A.clear(), mp.clear(), Lca.clear(), R.clear();
    C.resize(3*n, 1), Dt.resize(3*n), Ft.resize(3*n), Bit.resize(3*n), A.resize(3*n), Lca.resize(3*n, vector<int>(lg+1)), R.resize(3*n, 1);
    m=n-1, time_=1;
}
void dfs(int u, int p){
    Dt[u]=time_++;
    Lca[u][0]=p;
    for(int j=1;j<=lg;j++){
        Lca[u][j]=Lca[Lca[u][j-1]][j-1];
    }
    for(int i=0;i<A[u].size();i++){
        int v=A[u][i];
        if(v!=p)
            dfs(v, u);
    }
    Ft[u]=time_++;
}
int g(int i){
    return i-(i&(-i));
}
int h(int i){
    return i+(i&(-i));
}
void inc(int ind, int delta){
    while(ind<=2*n){
        Bit[ind]+=delta;
        ind=h(ind);
    }
}
int get(int ind){
    int sum=0;
    while(ind>=1){
        sum+=Bit[ind];
        ind=g(ind);
    }
    return sum;
}
int find_root(int u){
    int lca=u;
    for(int j=lg;j>=0;j--){
        if(get(Dt[u])==get(Dt[Lca[lca][j]]))
            lca=Lca[lca][j];
    }
    return lca;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q1>>q2;
    pre();
    int cnt=1;
    while(m--){
        int u, v;
        cin>>u>>v;
        A[u].push_back(v);
        A[v].push_back(u);
        mp[cnt++]={u, v};
    }
    dfs(1, 1);
    for(int i=1;i<=n;i++){
        inc(Dt[i], 1);
        inc(Ft[i], -1);
    }
    vector<bool>Active(n);
    while(q1--){
        int id;
        cin>>id;
        int u=mp[id].FF, v=mp[id].SS;
        if(Lca[u][0]==v)
            swap(u, v);
        if(!Active[id]){
            int root=find_root(u);
            R[root]+=R[v], C[root]+=R[v];
            R[v]=0, C[v]=C[root];
            inc(Dt[v], -1);
            inc(Ft[v], 1);
        }
        else if(Active[id]){
            int root=find_root(u);
            C[v]=C[root];
            inc(Dt[v], 1);
            inc(Ft[v], -1);
        }
        Active[id]=!Active[id];
    }
    while(q2--){
        int x;
        cin>>x;
        int ans=C[find_root(x)];
        cout<<ans<<endl;
    }
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40