oj.uz

Submission #768295

# Submission time Handle Problem Language Result Execution time Memory
768295 2023-06-27T21:18:09 Z Essa2006 Synchronization (JOI13_synchronization) C++14
30 / 100
 354 ms 91324 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();
    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;
}

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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 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 9168 KB Output is correct
8 Correct 17 ms 9140 KB Output is correct
9 Correct 18 ms 9160 KB Output is correct
10 Correct 354 ms 89316 KB Output is correct
11 Correct 316 ms 89352 KB Output is correct
12 Correct 293 ms 91324 KB Output is correct
13 Correct 223 ms 89208 KB Output is correct
14 Correct 232 ms 87996 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 89160 KB Output is correct
2 Correct 142 ms 87124 KB Output is correct
3 Correct 162 ms 89836 KB Output is correct
4 Correct 153 ms 90976 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

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 -