oj.uz

Submission #807038

# Submission time Handle Problem Language Result Execution time Memory
807038 2023-08-04T12:37:47 Z Hakiers Synchronization (JOI13_synchronization) C++17
100 / 100
 570 ms 25728 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]] + 1, pre[u]) >= (depth[u] - depth[jmp[v][k]]))
            v = jmp[v][k];
    }

    if(query(pre[v], pre[u]) == (depth[u] - depth[v]))
        return v;
    
    return u;
}

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];
        }
        else{
            int u = wsk[x];
            a[u] = b[u] = a[find(u)];
            update(pre[u], 0);
            update(post[u], 0);

        }
        active[x] ^=1;
    }

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

}

Subtask #1
10.0 / 10.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 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 34 ms 4144 KB Output is correct
8 Correct 26 ms 4236 KB Output is correct
9 Correct 25 ms 4240 KB Output is correct
10 Correct 312 ms 17488 KB Output is correct
11 Correct 367 ms 17496 KB Output is correct
12 Correct 329 ms 23136 KB Output is correct
13 Correct 269 ms 17564 KB Output is correct
14 Correct 206 ms 17088 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 20148 KB Output is correct
2 Correct 178 ms 19808 KB Output is correct
3 Correct 168 ms 22764 KB Output is correct
4 Correct 169 ms 22732 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 5 ms 2900 KB Output is correct
7 Correct 45 ms 4796 KB Output is correct
8 Correct 515 ms 23360 KB Output is correct
9 Correct 543 ms 23268 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 23252 KB Output is correct
2 Correct 414 ms 23636 KB Output is correct
3 Correct 404 ms 25688 KB Output is correct
4 Correct 426 ms 25728 KB Output is correct

Subtask #5
40.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 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 5 ms 2900 KB Output is correct
6 Correct 52 ms 4180 KB Output is correct
7 Correct 570 ms 17672 KB Output is correct
8 Correct 518 ms 23300 KB Output is correct
9 Correct 435 ms 18516 KB Output is correct
10 Correct 394 ms 20108 KB Output is correct
11 Correct 361 ms 23336 KB Output is correct
12 Correct 359 ms 23224 KB Output is correct
13 Correct 415 ms 25712 KB Output is correct