oj.uz

Submission #806957

# Submission time Handle Problem Language Result Execution time Memory
806957 2023-08-04T11:32:40 Z Hakiers Synchronization (JOI13_synchronization) C++17
0 / 100
 592 ms 23324 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 7;
const int BASE = 1 << 18;
const int LOG = 17;
vector<pair<int, int>> G[MAXN];
int TREE[BASE << 1];
int jmp[MAXN][LOG  + 1];
int a[MAXN], b[MAXN];
int depth[MAXN];
int pre[MAXN], post[MAXN];
int wsk[MAXN];
bool active[MAXN];
int tajm;
int n, m, q;

void dfs(int v, int p, int d = 0){

    pre[v] = ++tajm;
    jmp[v][0] = p;
    depth[v] = d;

    for(int k = 1; k <= LOG; k++)
        jmp[v][k] = jmp[jmp[v][k-1]][k-1];
    
    for(auto [u, id] : G[v]){
        if(u == p) continue;
        wsk[id] = u;
        dfs(u, v, d+1);
    }

    post[v] = ++tajm;
}

void update(int v, int val){

    v += BASE;
    TREE[v] = val;

    v/=2;

    while(v > 0){
        int l = 2*v, r = 2*v + 1;
        TREE[v] = TREE[l] + TREE[r];

        v/=2;
    }
}

int query(int a, int b){

    a += BASE - 1;
    b += BASE + 1;
    int res = 0;

    while(a/2 != b/2){
        if(a % 2 == 0) res += TREE[a+1];
        if(b % 2 == 1) res += TREE[b-1];

        a/=2; b/=2;
    }

    return res;
}

int find(int u){

    int v = u;

    for(int k = LOG; k >= 0; k--){
        if(query(pre[jmp[v][k]], pre[u]) == (depth[u] - depth[jmp[v][k]]))
            v = jmp[v][k];
    }
    
    return v;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;

    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        G[a].push_back({b, i});
        G[b].push_back({a, i});
    }

    dfs(1, 1);
    for(int i = 1; i <= n; i++) a[i] = 1;

    for(int i = 1; i <= m; i++){
        int x;

        cin >> x;

        if(!active[x]){
            int u = wsk[x];
            update(pre[u], 1);
            update(post[u], -1);
            int v = find(u);
            
            a[v] = a[v] + a[u] - b[u];
            a[u] = 0;
        }
        else{
            int u = wsk[x];
            update(pre[u], 0);
            update(post[u], 0);
            
            a[u] = b[u] = a[find(jmp[u][0])];

        }
        active[x] ^=1;
    }

    for(int i = 1; i <= q; i++){
        int x;
        cin >> x;
        cout << a[find(x)] << endl;
    }

}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

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