oj.uz

Submission #859900

# Submission time Handle Problem Language Result Execution time Memory
859900 2023-10-11T04:45:57 Z TS_2392 Synchronization (JOI13_synchronization) C++14
100 / 100
 213 ms 25288 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define dbg(x) cout << #x << " = " << (x) << ' '
using namespace std;
const int N = 1e5 + 3;
int n, m, q, tin[N], tout[N], timer;
int jmp[N][17], bit[2 * N], f[N], last_del[N];
bool stat[N];
vector<int> adj[N];
pair<int, int> edge[N];
void dfs(int u, int par){
    tin[u] = ++timer;
    for(int &v : adj[u]) if(v != par){
        jmp[v][0] = u;
        for(int i = 1; i < 17; ++i) if(jmp[v][i - 1]){
            jmp[v][i] = jmp[jmp[v][i - 1]][i - 1];
        }
        dfs(v, u);
    }
    tout[u] = ++timer;
}
void update(int i, int v){
    for(; i <= timer; i += i & -i) bit[i] += v;
}
int query(int i){
    int res = 0;
    for(; i >= 1; i -= i & -i) res += bit[i];
    return res;
}
int get_root(int node) {
    int lca = node;
    for (int i = 16; ~i; i--) {
        if (jmp[lca][i] && query(tin[jmp[lca][i]]) == query(tin[node])) lca = jmp[lca][i];
    }
    return lca;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m >> q;
    for(int i = 1; i < n; ++i){
        cin >> edge[i].fi >> edge[i].se;
        adj[edge[i].fi].eb(edge[i].se);
        adj[edge[i].se].eb(edge[i].fi);
    }
    dfs(1, 0);
    for(int i = 1; i < n; ++i){
        if(jmp[edge[i].fi][0] == edge[i].se) swap(edge[i].fi, edge[i].se);
    }
    for(int i = 1; i <= n; ++i){
        f[i] = 1;
        update(tin[i], -1);
        update(tout[i], 1);
    }
    while(m--){
        int id, u, v, root_u; cin >> id;
        tie(u, v) = edge[id]; root_u = get_root(u);
        if(stat[id] == 0){
            f[root_u] = f[root_u] + f[v] - last_del[v];
            update(tin[v], 1); update(tout[v], -1);
        }
        else{
            last_del[v] = f[v] = f[root_u];
            update(tin[v], -1); update(tout[v], 1);
        }
        stat[id] = !stat[id];
    }
    while(q--){
        int u; cin >> u;
        cout << f[get_root(u)] << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 8 ms 7104 KB Output is correct
8 Correct 8 ms 7004 KB Output is correct
9 Correct 9 ms 7100 KB Output is correct
10 Correct 99 ms 15708 KB Output is correct
11 Correct 103 ms 15956 KB Output is correct
12 Correct 149 ms 24144 KB Output is correct
13 Correct 49 ms 18112 KB Output is correct
14 Correct 72 ms 17552 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 19028 KB Output is correct
2 Correct 60 ms 20752 KB Output is correct
3 Correct 75 ms 23572 KB Output is correct
4 Correct 75 ms 23564 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6488 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 14 ms 7956 KB Output is correct
8 Correct 190 ms 24916 KB Output is correct
9 Correct 190 ms 24912 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 22096 KB Output is correct
2 Correct 115 ms 24656 KB Output is correct
3 Correct 116 ms 24912 KB Output is correct
4 Correct 117 ms 25016 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 11 ms 7196 KB Output is correct
7 Correct 129 ms 19056 KB Output is correct
8 Correct 206 ms 25288 KB Output is correct
9 Correct 65 ms 19016 KB Output is correct
10 Correct 83 ms 18776 KB Output is correct
11 Correct 84 ms 22096 KB Output is correct
12 Correct 84 ms 22312 KB Output is correct
13 Correct 113 ms 24912 KB Output is correct