oj.uz

Submission #769863

# Submission time Handle Problem Language Result Execution time Memory
769863 2023-06-30T11:46:53 Z Essa2006 Synchronization (JOI13_synchronization) C++14
100 / 100
 449 ms 35588 KB 
#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

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.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 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 596 KB Output is correct
7 Correct 17 ms 3016 KB Output is correct
8 Correct 21 ms 3016 KB Output is correct
9 Correct 17 ms 3028 KB Output is correct
10 Correct 300 ms 28564 KB Output is correct
11 Correct 301 ms 28476 KB Output is correct
12 Correct 333 ms 34704 KB Output is correct
13 Correct 216 ms 28460 KB Output is correct
14 Correct 202 ms 28000 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 31512 KB Output is correct
2 Correct 132 ms 31036 KB Output is correct
3 Correct 151 ms 34068 KB Output is correct
4 Correct 144 ms 34052 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 316 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 22 ms 3784 KB Output is correct
8 Correct 449 ms 35588 KB Output is correct
9 Correct 396 ms 35404 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 35472 KB Output is correct
2 Correct 186 ms 34980 KB Output is correct
3 Correct 182 ms 35324 KB Output is correct
4 Correct 216 ms 35296 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 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 548 KB Output is correct
6 Correct 21 ms 3172 KB Output is correct
7 Correct 367 ms 29328 KB Output is correct
8 Correct 439 ms 35480 KB Output is correct
9 Correct 217 ms 29504 KB Output is correct
10 Correct 258 ms 29344 KB Output is correct
11 Correct 178 ms 32672 KB Output is correct
12 Correct 170 ms 32648 KB Output is correct
13 Correct 196 ms 35316 KB Output is correct