제출 #1138108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138108		VMaksimoski008	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	279 ms	46612 KiB

Main

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 5;

struct union_find {
    int n;
    vector<int> par, size, mx;
    union_find(int _n) : n(_n), par(n+1), size(n+1, 1), mx(n+1) {
        for(int i=1; i<=n; i++) par[i] = mx[i] = i;
    }

    int find(int u) {
        if(u == par[u]) return u;
        return par[u] = find(par[u]);
    }

    void uni(int a, int b, int M) {
        a = find(a); b = find(b);
        if(a == b) return ;
        if(size[a] < size[b]) swap(a, b);
        par[b] = a;
        size[a] += size[b];
        mx[a] = M;
    }

    int get(int u) { 
        return mx[find(u)]; 
    }
};

int n, P[maxn], T[maxn][20], up[maxn][20], dep[maxn];
vector<int> G[maxn];

void dfs(int u, int p) {
    for(int i=1; i<20; i++) up[u][i] = up[ up[u][i-1] ][i-1];

    for(int v : G[u]) {
        if(v == p) continue;
        dep[v] = dep[u] + 1;
        up[v][0] = u;
        dfs(v, u);
    }
}

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

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

signed main() {
    cin >> n;
    for(int i=1; i<=n; i++) cin >> P[i];
    
    for(int i=0; i<n-1; i++) {
        int a, b; cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    dfs(1, 1);

    vector<ll> dp(n+1);

    vector<pii> ord;
    for(int i=1; i<=n; i++) ord.push_back({ P[i], i });
    sort(ord.begin(), ord.end());
    dp[ord[0].second] = 0;

    union_find dsu(n);
    for(auto [_, u] : ord) {
        // cout << "at " << u << '\n';
        for(int v : G[u]) {
            if(P[v] > P[u]) continue;
            // cout << "to " << v << '\n';
            int mx = dsu.get(v);
            // cout << "! " << mx << " " << dist(mx, u) << endl;
            dp[u] = max(dp[u], dp[mx] + dist(mx, u));
            dsu.uni(u, v, u);
        }
    }

    // for(int i=1; i<=n; i++) cout << dp[i] << " ";
    // cout << '\n';
    cout << dp[ord.back().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