oj.uz

Submission #768300

# Submission time Handle Problem Language Result Execution time Memory
768300 2023-06-27T21:21:39 Z Essa2006 Synchronization (JOI13_synchronization) C++14
30 / 100
 344 ms 91084 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();
    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];
}

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 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 2 ms 1192 KB Output is correct
7 Correct 18 ms 8916 KB Output is correct
8 Correct 22 ms 8944 KB Output is correct
9 Correct 19 ms 8916 KB Output is correct
10 Correct 344 ms 86988 KB Output is correct
11 Correct 302 ms 86976 KB Output is correct
12 Correct 342 ms 89132 KB Output is correct
13 Correct 193 ms 87228 KB Output is correct
14 Correct 229 ms 86188 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 89212 KB Output is correct
2 Correct 147 ms 86968 KB Output is correct
3 Correct 171 ms 89804 KB Output is correct
4 Correct 152 ms 89284 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 318 ms 91084 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 -