oj.uz

Submission #871043

# Submission time Handle Problem Language Result Execution time Memory
871043 2023-11-09T18:42:31 Z wksp Synchronization (JOI13_synchronization) C++14
50 / 100
 484 ms 28020 KB 
#include<bits/stdc++.h>

using namespace std;

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

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);
        if(lvl[v] - line_v  == lvl[jump[i][v]] - get_line(range[jump[i][v]].first + base)){
            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

# Verdict Execution time Memory 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 14996 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 5 ms 14940 KB Output is correct
7 Correct 32 ms 15604 KB Output is correct
8 Correct 33 ms 15452 KB Output is correct
9 Correct 31 ms 15448 KB Output is correct
10 Correct 351 ms 21088 KB Output is correct
11 Correct 367 ms 21328 KB Output is correct
12 Correct 372 ms 27032 KB Output is correct
13 Correct 248 ms 20920 KB Output is correct
14 Correct 189 ms 20264 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 23992 KB Output is correct
2 Correct 261 ms 24168 KB Output is correct
3 Correct 143 ms 26496 KB Output is correct
4 Correct 146 ms 26436 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory 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 Incorrect 2 ms 14940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 28020 KB Output is correct
2 Correct 259 ms 27632 KB Output is correct
3 Correct 247 ms 27656 KB Output is correct
4 Correct 249 ms 27928 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14996 KB Output is correct
3 Incorrect 2 ms 14940 KB Output isn't correct
4 Halted 0 ms 0 KB -