Submission #768299

#	Time	Username	Problem	Language	Result	Execution time	Memory
768299		Essa2006	Synchronization (JOI13_synchronization)	C++14	60 / 100	419 ms	93236 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;
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();
    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));
    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();
    if(q2==1){
        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};
        }
        vector<bool>Active(n);
        vector<int>Q1(q1);
        for(int i=0;i<q1;i++){
            cin>>Q1[i];
        }
        int node;
        cin>>node;
        dfs(node, node);
        for(int i=1;i<=n;i++){
            inc(Dt[i], 1);
            inc(Ft[i], -1);
        }
        for(int i=0;i<q1;i++){
            int id=Q1[i];
            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);
                C[root]+=C[v];
                C[v]=0;
                inc(Dt[v], -1);
                inc(Ft[v], 1);
            }
            else if(Active[id]){
                inc(Dt[v], 1);
                inc(Ft[v], -1);
            }
            Active[id]=!Active[id];
        }
        cout<<C[node]<<endl;
    }
    else{
        int cnt=1;
        while(m--){
            int u, v;
            cin>>u>>v;
            if(u>v)
                swap(u, v);
            A[u].push_back(v);
            A[v].push_back(u);
            mp[cnt++]={u, v};
        }
        vector<int>Mnf(n+1), Mxf(n+1);
        for(int i=1;i<=n;i++){
            Mnf[i]=Mxf[i]=i;
        }
        set<array<int, 2>>S;
        for(int i=1;i<=n;i++){
            S.insert({i, i});
        }
        vector<bool>Active(n);
        while(q1--){
            int id;
            cin>>id;
            int u=mp[id].FF, v=mp[id].SS;
            int L=u, R=v;
            array<int, 2>a={u, inf};
            auto it=S.upper_bound(a);
            a=*--it;
            L=a[0];
            a={v, inf};
            it=S.upper_bound(a);
            a=*--it;
            R=a[1];
            if(!Active[id]){
                Mxf[L]=Mxf[R], Mnf[R]=Mnf[L];
                a={u, inf};
                it=S.upper_bound(a);
                S.erase(--it);
                a={v, inf};
                it=S.upper_bound(a);
                S.erase(--it);
                S.insert({L, R});
            }
            else{
                Mnf[u]=Mnf[v]=Mnf[L];
                Mxf[u]=Mxf[v]=Mxf[R];
                a={L, R};
                S.erase(a);
                S.insert({L, u});
                S.insert({v, R});
            }
            Active[id]=!Active[id];
        }
        for(int i=2;i<=n;i++){
            Mxf[i]=max(Mxf[i], Mxf[i-1]);
        }
        for(int i=n-1;i>=1;i--){
            Mnf[i]=min(Mnf[i], Mnf[i+1]);
        }
        while(q2--){
            int x;
            cin>>x;
            cout<<Mxf[x]-Mnf[x]+1<<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: 0 / 40