oj.uz

Submission #950843

# Submission time Handle Problem Language Result Execution time Memory
950843 2024-03-20T19:28:11 Z Ahmed57 Synchronization (JOI13_synchronization) C++17
100 / 100
 334 ms 25032 KB 
#include "bits/stdc++.h"

using namespace std;
int in[100001],outt[100001];
int P[100001][20];
int bit[100001],dep[100001],ans[100001];
int n;vector<int> adj[100001];
int timer =0 ;
void add(int x,int v){
    while(x<=n){
        bit[x]+=v;
        x+=x&-x;
    }
}
int sum(int x){
    int ret = 0;
    while(x>=1){
        ret+=bit[x];
        x-=x&-x;
    }
    return ret;
}
void dfs(int x,int pr){
    in[x] = ++timer;
    P[x][0] = pr;
    dep[x] = dep[pr]+1;
    for(int j = 1;j<20;j++){
        P[x][j] = P[P[x][j-1]][j-1];
    }
    for(auto j:adj[x]){
        if(j==pr)continue;
        dfs(j,x);
    }
    outt[x] = timer;
}
int find(int x){
    int no = sum(in[x]);
    for(int j = 19;j>=0;j--){
        if(P[x][j]==0)continue;
        if(sum(in[P[x][j]])==no){
            x = P[x][j];
        }
    }
    return x;
}
void se(int x){
    add(in[x],1);
    add(outt[x]+1,-1);
}
void re(int x){
    add(in[x],-1);
    add(outt[x]+1,1);
}
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int m,q;cin>>n>>m>>q;
    int vis[n] = {0};
    int lol[n] = {0};
    vector<pair<int,int>> ed;

    for(int i = 0;i<n-1;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        ed.push_back({a,b});
        vis[i] = 0;
    }
    dfs(1,0);
    for(int i = 0;i<n-1;i++){
        if(dep[ed[i].first]<dep[ed[i].second])swap(ed[i].first,ed[i].second);
    }
    for(int i = 1;i<=n;i++){
        ans[i] = 1;
        add(in[i],1);
        add(outt[i]+1,-1);
    }
    for(int i = 0;i<m;i++){
        int x;cin>>x;x--;
        if(vis[x]==0){
            int cost = -lol[x]+ans[find(ed[x].second)]+ans[ed[x].first];
            re(ed[x].first);
            ans[find(ed[x].second)] = cost;
        }else{
            lol[x] = ans[find(ed[x].second)];
            ans[ed[x].first] = lol[x];
            se(ed[x].first);
        }
        vis[x] = !vis[x];
    }
    for(int i = 0;i<q;i++){
        int x;cin>>x;
        cout<<ans[find(x)]<<endl;
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4960 KB Output is correct
2 Correct 2 ms 4696 KB Output is correct
3 Correct 1 ms 4744 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 10 ms 7608 KB Output is correct
8 Correct 10 ms 7516 KB Output is correct
9 Correct 11 ms 7772 KB Output is correct
10 Correct 149 ms 19628 KB Output is correct
11 Correct 126 ms 19652 KB Output is correct
12 Correct 193 ms 24108 KB Output is correct
13 Correct 58 ms 19488 KB Output is correct
14 Correct 89 ms 18880 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 21700 KB Output is correct
2 Correct 79 ms 21440 KB Output is correct
3 Correct 93 ms 23580 KB Output is correct
4 Correct 93 ms 23496 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Correct 26 ms 8080 KB Output is correct
8 Correct 330 ms 25024 KB Output is correct
9 Correct 333 ms 25028 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 25032 KB Output is correct
2 Correct 254 ms 24608 KB Output is correct
3 Correct 240 ms 24672 KB Output is correct
4 Correct 241 ms 24776 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 3 ms 4700 KB Output is correct
6 Correct 23 ms 7464 KB Output is correct
7 Correct 316 ms 20424 KB Output is correct
8 Correct 334 ms 24928 KB Output is correct
9 Correct 178 ms 20668 KB Output is correct
10 Correct 225 ms 20396 KB Output is correct
11 Correct 201 ms 22980 KB Output is correct
12 Correct 202 ms 22976 KB Output is correct
13 Correct 244 ms 24776 KB Output is correct