Submission #49098728

---

Source Code Expand

/**
 *  @the_hyp0cr1t3
 *  06.01.2024 17:56
**/
#include <bits/stdc++.h>

struct DSU {
    std::vector<int> e;
    DSU(int n) : e(n, -1) {}

    int leader(int u) {
        return e[u] < 0 ? u : e[u] = leader(e[u]);
    }

    int size(int u) { return -e[leader(u)]; }
    bool same(int u, int v) { return leader(u) == leader(v); }

    bool merge(int u, int v) {
        u = leader(u), v = leader(v);
        if (u == v) return false;
        if (-e[u] < -e[v]) std::swap(u, v);
        e[u] += e[v];
        e[v] = u;
        return true;
    }
};

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

    int n, m;
    std::cin >> n >> m;
    std::vector<int> a(n);
    for (auto &x : a)
        std::cin >> x;
    std::vector<std::pair<int, int>> edges(m);
    DSU dsu(n);
    for (auto &[u, v] : edges) {
        std::cin >> u >> v;
        --u, --v;
        if (a[u] == a[v])
            dsu.merge(u, v);
    }

    for (auto &[u, v] : edges) {
        u = dsu.leader(u);
        v = dsu.leader(v);
        if (u == v) continue;
        if (a[u] > a[v]) std::swap(u, v);
    }
    
    std::ranges::sort(edges, {}, [&](const auto &x) {
        return a[x.first];
    });

    int st = dsu.leader(0), en = dsu.leader(n - 1);
    if (st == en) {
        std::cout << 1 << '\n';
        return 0;
    }

    std::vector<int> dp(n, -1e9);
    dp[st] = 1;
    dp[en] = 0;

    for (auto &[u, v] : edges) {
        if (u == v) continue;
        dp[v] = std::max(dp[v], dp[u] + 1);
    }

    std::cout << dp[en] << '\n';
}

Submission Info

Judge Result