Submission #924627

#	Time	Username	Problem	Language	Result	Execution time	Memory
924627		esomer	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	395 ms	68436 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct DSU
{
    vector<int> v;
    vector<pair<int, int>> mx;
    void init(int n, vector<int>& a){
        v.assign(n, -1);
        mx.resize(n);
        for(int i = 0; i < n; i++){
            mx[i] = {a[i], i};
        }
    }
    int get(int x){return v[x] < 0 ? x : v[x] = get(v[x]);}
    void unite(int x, int y){
        x = get(x); y = get(y);
        if(x == y) return;
        if(v[x] > v[y]) swap(x, y);
        v[x] += v[y]; v[y] = x;
        mx[x] = max(mx[x], mx[y]);
    }
    int getMx(int x){
        x = get(x);
        return mx[x].second;
    }
};

const int LOG = 20;

vector<int> depth, parents;
vector<vector<int>> dp, adj;

void DFS(int x){
    for(int node : adj[x]){
        if(node != parents[x]){
            parents[node] = x;
            depth[node] = depth[x] + 1;
            DFS(node);
        }
    }
}

int kth(int x, int dist){
    for(int k = 0; k < LOG; k++){
        if((1 << k) & dist){
            x = dp[k][x];
        }
    }
    return x;
}

int lca(int a, int b){
    if(depth[a] > depth[b]) swap(a, b);
    b = kth(b, depth[b] - depth[a]);
    if(a==b) return a;
    int anc = a;
    for(int k = LOG - 1; k >= 0; k--){
        if(dp[k][a] == dp[k][b]) anc = dp[k][a];
        else{
            a = dp[k][a];
            b = dp[k][b];
        }
    }
    return anc;
}

int getDist(int a, int b){
    int anc = lca(a, b);
    return depth[a] + depth[b] - 2 * depth[anc];
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    vector<pair<int, int>> P(N);
    vector<int> a(N);
    for(int i = 0; i < N; i++){
        int x; cin >> x;
        P[i] = {x, i};
        a[i] = x;
    }
    DSU UF; UF.init(N, a);
    adj.resize(N);
    for(int i = 0; i < N - 1; i++){
        int u, v; cin >> u >> v; u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    parents.assign(N, -1);
    depth.assign(N, 0);
    DFS(0);
    dp.assign(LOG, vector<int>(N));
    for(int k = 0; k < LOG; k++){
        for(int i = 0; i < N; i++){
            if(k == 0) dp[k][i] = parents[i];
            else{
                if(dp[k-1][i] == -1) dp[k][i] = -1;
                else dp[k][i] = dp[k-1][dp[k-1][i]];
            }
        }
    }
    sort(P.begin(), P.end());
    vector<int> ans(N, 0);
    for(pair<int, int> p : P){
        int i = p.second;
        for(int node : adj[i]){
            if(a[node] > a[i]) continue;
            ans[i] = max(ans[i], ans[UF.getMx(node)]+getDist(i, UF.getMx(node)));
            UF.unite(i, node);
        }
    }
    cout << ans[P[N-1].second] << "\n";
}

• 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