Submission #1199874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199874		Boomyday	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	261 ms	49872 KiB

Main

//
// Created by adavy on 5/11/2025.
//
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

vector<vector<int>> adj;
// to calculate distances
vector<vector<int>> par; vector<int> dep;

void dfs(int u, int p){
    par[u][0] = p;
    for(auto&v:adj[u]) if (v != p){
            dep[v] = dep[u] + 1;
            dfs(v,u);
    }
}

int lca(int a, int b){
    if (dep[a] < dep[b]) swap(a,b);
    // dep[a] >= dep[b]
    for(int j=0;j<20;++j) if ((1<<j)&(dep[a]-dep[b])) a = par[a][j];
    if (a == b) return a;
    for(int j=19;j>=0;--j) if (par[a][j] != par[b][j]){
            a = par[a][j];
            b = par[b][j];
    }
    return par[a][0];
}

int dist(int a, int b){
    return dep[a] + dep[b] - 2*dep[lca(a,b)];
}

struct dsu{
    vector<int> rep;
    vector<int> key;
    dsu(int n){
        rep.resize(n);
        key.resize(n);
        for(int i=0;i<n;++i){
            rep[i] = i;
            key[i] = i;
        }
    }
    int find(int u){
        if (rep[u] == u) return u;
        return rep[u] = find(rep[u]);
    }
    void unite(int a, int b){
        // a is the new key
        if (find(a) == find(b)) return;
        int fa = find(a);
        int fb = find(b);
        rep[fb] = fa;
        key[fa] = a;
    }
    int get_key(int u){
        return key[find(u)];
    }
};
int main(){
    int N; cin >> N;
    adj.resize(N);
    vector<int> height(N);
    par.resize(N, vector<int>(20, -1));
    dep.resize(N, 0);
    for(int i=0;i<N;++i){
        cin >> height[i];
    }
    for(int i=0;i<(N-1);++i){
        int a, b; cin >> a >> b; a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    // calculate distances
    dfs(0, -1);
    for(int j=1;j<20;++j){
        for(int i=0;i<N;++i){
            if (par[i][j-1] != -1){
                par[i][j] = par[par[i][j-1]][j-1];
            }
        }
    }

    vector<int> order;
    for(int i=0;i<N;++i){
        order.push_back(i);
    }
    sort(order.begin(), order.end(), [&](int a, int b){
        return height[a] < height[b];
    });

    vector<ll> dp(N, 0);
    dsu d(N);
    for(auto&u:order){
        for(auto&v:adj[u]){
            if (height[v] > height[u]) continue;
            int keyv = d.get_key(v);
            dp[u] = max(dp[u], dist(u, keyv) + dp[keyv]);
            d.unite(u, v);
        }
    }
    cout << dp[order[N-1]] << endl;
}

• 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