Submission #769863

#	Time	Username	Problem	Language	Result	Execution time	Memory
769863		Essa2006	Synchronization (JOI13_synchronization)	C++14	100 / 100	449 ms	35588 KiB

synchronization

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int lg=18;
int n, m, q1, q2, time_;
vector<int>C, Dt, Ft, R, Bit;
vector<vector<int>>A, Lca;
map<int, pair<int, int>>mp;
void pre(){
    C.clear(), Dt.clear(), Ft.clear(), R.clear(), Bit.clear(), A.clear(), Lca.clear(), mp.clear();
    C.resize(n+1, 1), Dt.resize(n+1), Ft.resize(n+1), R.resize(n+1, 1), Bit.resize(2*n+1),  A.resize(n+1), Lca.resize(n+1, vector<int>(lg+1));
    m=n-1, time_=1;
}
int g(int i){
    return i-(i&(-i));
}
int h(int i){
    return i+(i&(-i));
}
int get(int ind){
    int res=0;
    while(ind>=1){
        res+=Bit[ind];
        ind=g(ind);
    }
    return res;
}
void inc(int ind, int delta){
    while(ind<=2*n){
        Bit[ind]+=delta;
        ind=h(ind);
    }
} 
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 find_root(int u){
    for(int j=lg;j>=0;j--){
        if(get(Dt[u])==get(Dt[Lca[u][j]])){
            u=Lca[u][j];
        }
    }
    return u;
}
int 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;
            inc(Dt[v], -1);
            inc(Ft[v], 1);
        }
        else{
            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(int, int)':
synchronization.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     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