oj.uz

Submission #768297

# Submission time Handle Problem Language Result Execution time Memory
768297 2023-06-27T21:20:08 Z Essa2006 Synchronization (JOI13_synchronization) C++14
60 / 100
 405 ms 95760 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<=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 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 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 18 ms 8916 KB Output is correct
9 Correct 18 ms 8916 KB Output is correct
10 Correct 309 ms 87060 KB Output is correct
11 Correct 304 ms 87048 KB Output is correct
12 Correct 301 ms 89088 KB Output is correct
13 Correct 189 ms 87100 KB Output is correct
14 Correct 224 ms 86204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 89116 KB Output is correct
2 Correct 140 ms 86908 KB Output is correct
3 Correct 165 ms 89820 KB Output is correct
4 Correct 153 ms 89288 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 28 ms 9800 KB Output is correct
8 Correct 381 ms 95700 KB Output is correct
9 Correct 405 ms 95760 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 93472 KB Output is correct
2 Correct 167 ms 94984 KB Output is correct
3 Correct 168 ms 95500 KB Output is correct
4 Correct 169 ms 95608 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 -