oj.uz

Submission #768299

# Submission time Handle Problem Language Result Execution time Memory
768299 2023-06-27T21:21:00 Z Essa2006 Synchronization (JOI13_synchronization) C++14
60 / 100
 419 ms 93236 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 18 ms 8916 KB Output is correct
8 Correct 17 ms 8916 KB Output is correct
9 Correct 18 ms 8916 KB Output is correct
10 Correct 309 ms 87048 KB Output is correct
11 Correct 305 ms 86988 KB Output is correct
12 Correct 318 ms 89128 KB Output is correct
13 Correct 196 ms 87232 KB Output is correct
14 Correct 223 ms 86208 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 89160 KB Output is correct
2 Correct 156 ms 87136 KB Output is correct
3 Correct 164 ms 89812 KB Output is correct
4 Correct 154 ms 89216 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 404 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 32 ms 9564 KB Output is correct
8 Correct 378 ms 92816 KB Output is correct
9 Correct 419 ms 92928 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 92876 KB Output is correct
2 Correct 163 ms 92544 KB Output is correct
3 Correct 175 ms 93208 KB Output is correct
4 Correct 164 ms 93236 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -