oj.uz

Submission #1110064

# Submission time Handle Problem Language Result Execution time Memory
1110064 2024-11-08T15:40:52 Z BF001 Synchronization (JOI13_synchronization) C++17
100 / 100
 1395 ms 40236 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define N 100005
#define int long long
#define log 16
#define fi first 
#define se second

typedef pair<int, int> ii;

int n, m, par[log + 2][N], dep[N], tin[N], tout[N], tim, bit[4 * N], lazy[4 * N], res[N], lst[N], q, vs[N];
ii eg[N];
vector<int> adj[N];
 
void add(int id, int l, int r, int val){
    bit[id] += val * (r - l + 1);
    lazy[id] += val;
}

void down(int id, int l, int r){
    if (l == r) return;
    int mid = (l + r) >> 1;
    add(id * 2, l, mid, lazy[id]);
    add(id * 2 + 1, mid + 1, r, lazy[id]);
    lazy[id] = 0; 
}

void ud(int id, int l, int r, int u, int v, int val){
    if (u > r || l > v) return;
    if (l >= u && r <= v){
        add(id, l, r, val);
        return;
    }
    down(id, l, r);
    int mid = (l + r) >> 1;
    ud(id * 2, l, mid, u, v, val);
    ud(id * 2 + 1, mid + 1, r, u, v, val);
    bit[id] = bit[id * 2] + bit[id * 2 + 1];
}

int get(int id, int l, int r, int pos){
    if (r < pos || l > pos) return 0;
    if (l == r) return bit[id];
    down(id, l, r);
    int mid = (l + r) >> 1;
    return get(id * 2, l, mid, pos) + get(id * 2 + 1, mid + 1, r, pos);
}

void dfs(int u, int p){
    par[0][u] = p;
    dep[u] = dep[p] + 1;
    tin[u] = ++tim;
    res[u] = 1;
    for (auto x : adj[u]){
        if (x == p) continue;
        dfs(x, u);
    }
    tout[u] = tim;
}

int go(int u){
    for (int k = log; k >= 0; k--){
        if (!par[k][u]) continue;
        if (get(1, 1, n, tin[u]) - get(1, 1, n, tin[par[k][u]]) == dep[u] - dep[par[k][u]]){
            u = par[k][u];
        }
    }
    return u;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    cin >> n >> m >> q;
    for (int i = 1; i <= n - 1; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        eg[i] = {u, v};
    }

    dfs(1, 0);
    for (int k = 1; k <= log; k++){
        for (int i = 1; i <= n; i++){
            par[k][i] = par[k - 1][par[k - 1][i]];
        }
    }

    for (int i = 1; i <= n - 1; i++){
        if (dep[eg[i].fi] > dep[eg[i].se]) swap(eg[i].fi, eg[i].se);
    }

    for (int i = 1; i <= m; i++){
        int u;
        cin >> u;
        if (vs[u]){
           res[eg[u].se] = lst[eg[u].se] = res[go(eg[u].se)];  
           ud(1, 1, n, tin[eg[u].se], tout[eg[u].se], -1); 
        }
        else{
           res[go(eg[u].fi)] += res[eg[u].se] - lst[eg[u].se];
           ud(1, 1, n, tin[eg[u].se], tout[eg[u].se], 1);
        }
        vs[u] ^= 1;
    }

    for (int i = 1; i <= n; i++){
        res[i] = res[go(i)];
    }

    while (q--){
        int u;
        cin >> u;
        cout << res[u] << "\n";
    }
 
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23376 KB Output is correct
2 Correct 3 ms 23120 KB Output is correct
3 Correct 4 ms 23120 KB Output is correct
4 Correct 3 ms 23120 KB Output is correct
5 Correct 5 ms 23180 KB Output is correct
6 Correct 6 ms 23120 KB Output is correct
7 Correct 43 ms 25936 KB Output is correct
8 Correct 41 ms 26100 KB Output is correct
9 Correct 42 ms 26072 KB Output is correct
10 Correct 715 ms 35368 KB Output is correct
11 Correct 631 ms 35144 KB Output is correct
12 Correct 1395 ms 39240 KB Output is correct
13 Correct 181 ms 35028 KB Output is correct
14 Correct 356 ms 34808 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 35012 KB Output is correct
2 Correct 424 ms 37020 KB Output is correct
3 Correct 703 ms 38792 KB Output is correct
4 Correct 717 ms 38796 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23120 KB Output is correct
2 Correct 3 ms 23288 KB Output is correct
3 Correct 3 ms 23180 KB Output is correct
4 Correct 4 ms 23120 KB Output is correct
5 Correct 4 ms 23120 KB Output is correct
6 Correct 8 ms 23120 KB Output is correct
7 Correct 81 ms 26460 KB Output is correct
8 Correct 1341 ms 40236 KB Output is correct
9 Correct 1321 ms 40196 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1333 ms 37144 KB Output is correct
2 Correct 818 ms 39760 KB Output is correct
3 Correct 733 ms 40008 KB Output is correct
4 Correct 705 ms 39808 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23120 KB Output is correct
2 Correct 3 ms 23288 KB Output is correct
3 Correct 3 ms 23120 KB Output is correct
4 Correct 4 ms 23120 KB Output is correct
5 Correct 5 ms 23120 KB Output is correct
6 Correct 42 ms 26120 KB Output is correct
7 Correct 539 ms 36164 KB Output is correct
8 Correct 1364 ms 40008 KB Output is correct
9 Correct 154 ms 36284 KB Output is correct
10 Correct 312 ms 36008 KB Output is correct
11 Correct 424 ms 38260 KB Output is correct
12 Correct 449 ms 38384 KB Output is correct
13 Correct 709 ms 40008 KB Output is correct