Submission #1274165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274165		MisterReaper	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	227 ms	40076 KiB

Main

// File catexercise.cpp created on 29.09.2025 at 14:27:20
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;

    std::vector<int> H(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> H[i];
    }

    std::vector<std::vector<int>> adj(N);
    for (int i = 1; i < N; ++i) {
        int A, B;
        std::cin >> A >> B;
        --A, --B;
        adj[A].emplace_back(B);
        adj[B].emplace_back(A);
    }

    const int LG = std::__lg(N) + 1;

    std::vector<int> dep(N);
    std::vector<std::vector<int>> par(LG, std::vector<int>(N));
    auto dfs = [&](auto&& self, int v) -> void {
        for (auto u : adj[v]) {
            if (u == par[0][v]) {
                continue;
            }
            dep[u] = dep[v] + 1;
            par[0][u] = v;
            self(self, u);
        }
    };
    dfs(dfs, 0);

    for (int l = 1; l < LG; ++l) {
        for (int i = 0; i < N; ++i) {
            par[l][i] = par[l - 1][par[l - 1][i]];
        }
    }

    auto lca = [&](int a, int b) -> int {
        if (dep[a] > dep[b]) {
            std::swap(a, b);
        }
        int dif = dep[b] - dep[a];
        for (int l = 0; l < LG; ++l) {
            if (dif >> l & 1) {
                b = par[l][b];
            }
        }
        if (a == b) {
            return a;
        }
        for (int l = LG - 1; l >= 0; --l) {
            if (par[l][a] != par[l][b]) {
                a = par[l][a];
                b = par[l][b];
            }
        }
        return par[0][a];
    };

    auto dis = [&](int a, int b) -> int {
        return dep[a] + dep[b] - 2 * dep[lca(a, b)];
    };

    std::vector<int> f(N);
    std::iota(f.begin(), f.end(), 0);
    auto get = [&](int x) -> int {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    };
    auto unite = [&](int a, int b) -> bool {
        a = get(a), b = get(b);
        if (a == b) {
            return false;
        }
        f[a] = b;
        return true;
    };

    std::vector<i64> ans(N);
    std::vector<int> act(N), ord(N);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](auto lhs, auto rhs) {
        return H[lhs] < H[rhs];
    });

    for (auto i : ord) {
        act[i] = true;
        for (auto j : adj[i]) {
            if (!act[j]) {
                continue;
            }
            j = get(j);
            ans[i] = std::max(ans[i], ans[j] + dis(i, j));
            unite(j, i);
        }
    }

    std::cout << ans[ord[N - 1]] << '\n';

    return 0;
}

• 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