Submission #884546

#	Time	Username	Problem	Language	Result	Execution time	Memory
884546		wksp	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	207 ms	64460 KiB

Main

#include<bits/stdc++.h>

using namespace std;
const int n_max = 2 * 1e5 + 7;
const int max_log = 20;
int jump[max_log][n_max];

vector<int> graph[n_max];
int graph_up[n_max];
vector<int> graph_down[n_max];
long long deep[n_max];
int open[n_max];
int leader[n_max];
long long ans[n_max];
void init(int n){
    for(int i = 0; i    <= n; i++){
        leader[i] = i;
    }
}
void init_DFS(int v, int p = 0, int vallue = 1){
    graph_up[v] = p;
    deep[v] = vallue;
    for(auto u: graph[v]){
        if(u != p){
            init_DFS(u, v, vallue + 1);
            graph_down[v].push_back(u);
        }
    }
}
void init_jumps(int n){
    for(int i = 1; i <= n; i++){
        jump[0][i] = graph_up[i];
    }
    for(int i = 1; i < max_log; i++){
        for(int j = 1; j <= n; j++){
            jump[i][j] = jump[i-1][jump[i-1][j]];
        }
    }
}

int find(int v){
    if(v != leader[v]){
        leader[v] = find(leader[v]);
    }
    return leader[v];
}
long long unite_without_lca(int v, int u){
    u = find(u);
    leader[u] = v;
    return (deep[u] - deep[v]) + ans[u];
}
long long get_lca(int v, int u){
    if(deep[v] > deep[u]){
        int tmp = v;
        v = u;
        u = tmp;
    }
    long long number = (1<<19);
    for(int i = 19; i > -1; i--){
        if(deep[u] - deep[v] >= number){
            u = jump[i][u];
        }
        number /= 2;
    }
    if(u == v){
        return v;
    }
    for(int i = 19; i > -1; i--){
        if(jump[i][u] != jump[i][v]){
            u = jump[i][u];
            v = jump[i][v];
        }
    }
    return jump[0][v];
}
long long unite_with_lca(int v, int u){
    u = find(u);
    int lca = get_lca(v, u);
    leader[u] = v;
    return (deep[u] + deep[v] - 2 * deep[lca] + ans[u]);
}

void add_point(int v){
    ans[v] = 0;
    open[v] = 1;
    if(open[graph_up[v]] == 1){
        ans[v] = unite_with_lca(v, graph_up[v]); 
    }
    for(auto u: graph_down[v]){
        if(open[u] == 1){
            ans[v] = max(ans[v], unite_without_lca(v, u));
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    vector<pair<int, int>> tower_hight;
    int n;
    cin >> n;
    init(n);
    for(int i = 1; i <= n; i++){
        int p;
        cin >> p;
        tower_hight.push_back({p, i});
    }
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    init_DFS(1);
    init_jumps(n);
    sort(tower_hight.begin(), tower_hight.end());
    for(auto [p, id]: tower_hight){
        add_point(id);
    }
    cout << ans[tower_hight[tower_hight.size()- 1].second] << '\n';

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:117:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  117 |     for(auto [p, id]: tower_hight){
      |              ^

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26