oj.uz

답안 #884553

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
884553 2023-12-07T16:29:04 Z wksp 동기화 (JOI13_synchronization) C++14
100 / 100
 570 ms 27984 KB 
#include<bits/stdc++.h>

using namespace std;

const int n_max = 1e5 + 7;
const int base = 131072;
// const int base = 4;

const int max_log = 20;  
int activated[n_max];
vector<int> graph[n_max];
pair<int, int> array_lines[n_max];
int jump[max_log + 2][n_max];
int date[n_max];
int common_date[n_max];
int lvl[n_max];
pair<int, int> range[n_max];
int tree[base*2];


void add(int a, int b, int vallue, int v = 1, int l = 0, int r = base - 1){
    if(a <= l and b >= r){
        tree[v] += vallue;
        return;
    }
    if(b < l or a > r){
        return;
    }
    int mid = (l+r)/2;
    add(a, b, vallue, v * 2, l, mid);
    add(a, b, vallue, v * 2 + 1, mid + 1, r);
}
int get_line(int v){
    if(v == 0){
        return 0;
    }
    return (get_line(v/2) + tree[v]); 
}

int find(int v){
    
    int number = (1<<(max_log-1));
    for(int i = max_log - 1; i >= 0; i--){
        int line_v = get_line(range[v].first + base);
        int line_v_jump = get_line(range[jump[i][v]].first + base);
        if(lvl[v] - line_v  == lvl[jump[i][v]] - line_v_jump){
            v = jump[i][v];
        }
        number /= 2;
    }
    return v;
}
void activate(pair<int, int> actual_line){
    int upper_point, lower_point;
    if(lvl[actual_line.first] < lvl[actual_line.second]){
        upper_point = actual_line.first;
        lower_point = actual_line.second;
    }else{
        upper_point = actual_line.second;
        lower_point = actual_line.first;
    }
    upper_point = find(upper_point);
    date[upper_point] = date[upper_point] + date[lower_point] - common_date[lower_point];
    add(range[lower_point].first, range[lower_point].second, 1);
}
void deactivate(pair<int, int> actual_line){
    int upper_point, lower_point;
    if(lvl[actual_line.first] < lvl[actual_line.second]){
        upper_point = actual_line.first;
        lower_point = actual_line.second;
    }else{
        upper_point = actual_line.second;
        lower_point = actual_line.first;
    }
    upper_point = find(upper_point);
    common_date[lower_point] = date[upper_point];
    date[lower_point] = date[upper_point];
    add(range[lower_point].first, range[lower_point].second, -1);
}
int DFS(int v, int p, int deep, int nr){
    lvl[v] = deep;
    range[v].first = nr;
    jump[0][v] = p;
    for(auto u: graph[v]){
        if(u != p){
            nr = DFS(u, v, deep + 1, nr + 1);
        }
    }
    range[v].second = nr;
    return nr;
}
void init(int n){
    DFS(1, 0, 1, 1);
    for(int i = 1; i < max_log; i++){
        for(int j = 0; j <= n; j++){
            jump[i][j] = jump[i-1][jump[i-1][j]];
        }
    }
    for(int i = 1; i <= n; i++){
        date[i] = 1;
    }
}
void print(int n){
    cout << "\nSYSTEM OUTPUT\n";
    for(int i = 0; i <= n; i++){
        cout << i << " " << lvl[i] << " " << range[i].first << ' ' << range[i].second << " " << date[i] << " " << date[find(i)] << '\n';
    }
}
void print_inner(int n){
    cout << "\nSYSTEM OUTPUT (INNER)\n";
    for(int i = 0; i <= n; i++){
        cout << i << " " << date[i] << " " << find(i) << " " << date[find(i)] << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
        array_lines[i] = {a, b};
    }
    init(n);
    for(int i = 0; i < m; i++){
        int line;
        cin >> line;
        if(activated[line] == 0){
            activate(array_lines[line]);
            activated[line] = 1;
        }else{
            deactivate(array_lines[line]);
            activated[line] = 0;
        }
        //print_inner(n);
    }
    for(int i = 0; i < q; i++){
        int v;
        cin >> v;
        v = find(v);
        cout << date[v] << '\n';
    }
    //print(n);

    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14988 KB Output is correct
6 Correct 5 ms 14940 KB Output is correct
7 Correct 32 ms 15452 KB Output is correct
8 Correct 31 ms 15452 KB Output is correct
9 Correct 31 ms 15452 KB Output is correct
10 Correct 508 ms 20980 KB Output is correct
11 Correct 339 ms 20608 KB Output is correct
12 Correct 353 ms 26968 KB Output is correct
13 Correct 293 ms 20460 KB Output is correct
14 Correct 181 ms 20312 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 253 ms 23684 KB Output is correct
2 Correct 254 ms 23632 KB Output is correct
3 Correct 145 ms 26452 KB Output is correct
4 Correct 150 ms 26212 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 6 ms 14940 KB Output is correct
7 Correct 42 ms 16220 KB Output is correct
8 Correct 504 ms 27860 KB Output is correct
9 Correct 570 ms 27984 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 472 ms 27472 KB Output is correct
2 Correct 256 ms 27388 KB Output is correct
3 Correct 249 ms 27480 KB Output is correct
4 Correct 257 ms 27476 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 3 ms 14936 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 6 ms 14940 KB Output is correct
6 Correct 43 ms 15656 KB Output is correct
7 Correct 464 ms 21904 KB Output is correct
8 Correct 465 ms 27692 KB Output is correct
9 Correct 378 ms 21568 KB Output is correct
10 Correct 304 ms 21504 KB Output is correct
11 Correct 381 ms 24764 KB Output is correct
12 Correct 370 ms 24732 KB Output is correct
13 Correct 248 ms 27380 KB Output is correct