oj.uz

Submission #533398

# Submission time Handle Problem Language Result Execution time Memory
533398 2022-03-05T21:20:24 Z Marceantasy Synchronization (JOI13_synchronization) C++17
0 / 100
 501 ms 26288 KB 
#include <bits/stdc++.h>
using namespace std; 
 
#define ll long long
#define ar array
 
const int mxN = 2e5+1, M = 1e9+7;
int n, m, q;
bool active[mxN];
 
vector<int> adj[mxN];
pair<int, int> edges[mxN];
int info[mxN], last_sync[mxN];
 
int timer = 0, tin[mxN], tout[mxN];
 
int up[20][mxN];
int bit[mxN];
 
void dfs(int u = 0, int p = -1){
    up[0][u] = p;
    for(int i = 1; i<20 && up[i-1][u]!=-1; ++i){
        up[i][u] = up[i-1][up[i-1][u]];
    }
    info[u] = 1;
    tin[u] = timer++;
    for(int v : adj[u]){
        if(v == p) continue;
        dfs(v, u);
    }
    tout[u] = timer++;
}
 
void upd(int pos, int val){
    for(; pos<n; pos = pos | (pos+1)){
        bit[pos] += val;
    }
}
 
int qry(int pos){
    int ans = 0;
    for(; pos>=0; pos = (pos & (pos+1))-1){
        ans += bit[pos];
    }
    return ans;
}
 
int ancestor(int u){
    int lca = u;
    for(int i = 19; i>=0; --i){
        if(up[i][u]!=-1 && qry(tin[up[i][lca]]) == qry(tin[u])){
            lca = up[i][lca];
        }
    }
    return lca;
}
 
int main(){
#ifdef _DEBUG
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
    std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
 
    cin >> n >> m >> q; 
    for(int i = 0; i<n-1; ++i){
        int a, b; 
        cin >> a >> b, --a, --b; 
        edges[i] = {a, b};
        adj[edges[i].first].push_back(edges[i].second);
        adj[edges[i].second].push_back(edges[i].first);
    }
    dfs();
    for(int i = 0; i<n; ++i){
        upd(tin[i], -1);
        upd(tout[i], 1);
    }
    while(m--){
        int x; 
        cin >> x, --x; 
        int u = edges[x].first, v = edges[x].second;
        if(active[x]){
            info[u] = info[v] = info[ancestor(u)];
            upd(tin[v], -1);
            upd(tout[v], 1);
        }else{
            info[ancestor(u)] += info[v] - last_sync[v];
            upd(tin[v], 1); 
            upd(tout[v], -1);
        }
        active[x] = active[x]^1;
    }
    while(q--){
        int x; 
        cin >> x, --x; 
        cout << info[ancestor(x)] << "\n";
    }
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5080 KB Output is correct
2 Incorrect 3 ms 5068 KB Output isn't correct
3 Halted 0 ms 0 KB -