oj.uz

답안 #859899

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
859899 2023-10-11T04:40:31 Z TS_2392 동기화 (JOI13_synchronization) C++14
0 / 100
 143 ms 22100 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 get_sum(int i){
    int res = 0;
    for(; i >= 1; i -= i & -i) res += bit[i];
    return res;
}
int get_root(int u){
    int path_root_u = get_sum(tin[u]);
    for(int i = 16; i >= 0; --i) if(jmp[u][i]){
        if(path_root_u - (1 << i) == get_sum(tin[jmp[u][i]])) u = jmp[u][i];
    }
    return (get_sum(tin[jmp[u][0]]) == get_sum(tin[u]) ? u : jmp[u][0]);
}
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);
    }
    fill(f + 1, f + 1 + n, 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];
        //dbg(root_u); dbg(u); dbg(v); dbg(f[root_u]); dbg(f[v]); EL;
    }
    while(q--){
        int u; cin >> u;
        //dbg(u); dbg(get_root(u));
        cout << f[get_root(u)] << '\n';
    }
    return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 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 1 ms 6488 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 8 ms 7004 KB Output is correct
8 Correct 8 ms 7004 KB Output is correct
9 Correct 8 ms 7000 KB Output is correct
10 Correct 92 ms 15912 KB Output is correct
11 Incorrect 92 ms 15904 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 19032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 143 ms 22100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 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 Incorrect 1 ms 6492 KB Output isn't correct
5 Halted 0 ms 0 KB -