oj.uz

Submission #769852

# Submission time Handle Problem Language Result Execution time Memory
769852 2023-06-30T11:14:01 Z Essa2006 Synchronization (JOI13_synchronization) C++14
100 / 100
 463 ms 95068 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, 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

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 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 20 ms 9172 KB Output is correct
8 Correct 20 ms 9164 KB Output is correct
9 Correct 20 ms 9172 KB Output is correct
10 Correct 351 ms 90116 KB Output is correct
11 Correct 348 ms 90232 KB Output is correct
12 Correct 388 ms 94196 KB Output is correct
13 Correct 221 ms 89964 KB Output is correct
14 Correct 232 ms 89552 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 91916 KB Output is correct
2 Correct 161 ms 90936 KB Output is correct
3 Correct 181 ms 93512 KB Output is correct
4 Correct 172 ms 93520 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 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 32 ms 9792 KB Output is correct
8 Correct 428 ms 94956 KB Output is correct
9 Correct 442 ms 95036 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 94956 KB Output is correct
2 Correct 233 ms 94152 KB Output is correct
3 Correct 230 ms 94696 KB Output is correct
4 Correct 242 ms 94704 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 24 ms 9332 KB Output is correct
7 Correct 394 ms 90972 KB Output is correct
8 Correct 463 ms 95068 KB Output is correct
9 Correct 244 ms 91048 KB Output is correct
10 Correct 290 ms 90756 KB Output is correct
11 Correct 194 ms 93124 KB Output is correct
12 Correct 196 ms 93136 KB Output is correct
13 Correct 234 ms 94856 KB Output is correct