Submission #871043

#	Time	Username	Problem	Language	Result	Execution time	Memory
871043		wksp	Synchronization (JOI13_synchronization)	C++14	50 / 100	484 ms	28020 KiB

synchronization

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 10
• Subtask 4: 20 / 20
• Subtask 5: 0 / 40