Submission #832879

#	Time	Username	Problem	Language	Result	Execution time	Memory
832879		vjudge1	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	433 ms	407996 KiB

Main

#include <bits/stdc++.h>
using namespace std;

/// 123

static const int N = 1e6 + 10;
class lca_t {
       public:
        int rmq[20][N * 2];
        int pos[N], d[N];
        vector<int> adj[N];
        int timer;
        int n;

        lca_t(int n = 0) : n(n) {}

        void add_edge(int u, int v) {
                adj[u].emplace_back(v);
                adj[v].emplace_back(u);
        }

        void dfs(int u, int p) {
                rmq[0][timer++] = u;
                for (int v : adj[u]) {
                        if (v == p) continue;
                        d[v] = d[u] + 1;
                        dfs(v, u);
                        rmq[0][timer++] = u;
                }
        }

        void build(int root) {
                timer = 0;
                d[root] = 0;
                dfs(root, -1);
                for (int i = 0; i < timer; i++) pos[rmq[0][i]] = i;
                assert(__lg(timer) < 20);
                for (int i = 1; i <= __lg(timer); i++) {
                        for (int j = 0; j + (1 << i) <= timer; j++) {
                                rmq[i][j] = d[rmq[i - 1][j]] < d[rmq[i - 1][j + (1 << (i - 1))]]
                                                ? rmq[i - 1][j]
                                                : rmq[i - 1][j + (1 << (i - 1))];
                        }
                }
        }

        int get(int u, int v) {
                int l = pos[u], r = pos[v];
                if (l > r) swap(l, r);
                int i = __lg(r - l + 1);
                r -= (1 << i) - 1;
                int x = d[rmq[i][l]] < d[rmq[i][r]] ? rmq[i][l] : rmq[i][r];
                return d[u] + d[v] - d[x] * 2;
        }

} lca;

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        vector<vector<int>> adj(n);
        lca = lca_t(n);
        for (int i = 0; i < n - 1; i++) {
                int u, v;
                cin >> u >> v;
                u--, v--;
                if (a[u] < a[v]) swap(u, v);
                adj[u].emplace_back(v);
                lca.add_edge(u, v);
        }
        vector<int> ord(n);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int i, int j) {
                return a[i] < a[j];
        });
        lca.build(0);
        vector<int> par(n, -1), m(n, -1);
        vector<int64_t> f(n, 0);
        for (int i = 0; i < n; i++) m[i] = i;
        function<int(int)> root = [&](int u) { return par[u] < 0 ? u : (par[u] = root(par[u])); };
        function<void(int, int)> unite = [&](int u, int v) {
                u = root(u), v = root(v);
                if (a[m[u]] < a[m[v]]) swap(u, v);
                int64_t ff = max(f[u], f[v] + lca.get(m[u], m[v]));
                if (par[u] > par[v]) swap(u, v);
                if (a[m[u]] < a[m[v]]) m[u] = m[v];
                par[u] += par[v];
                par[v] = u;
                f[u] = ff;
        };
        for (int i : ord) {
                for (int j : adj[i]) unite(i, j);
        }
        cout << f[root(0)];
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:7:7: warning: '<anonymous>.lca_t::timer' may be used uninitialized in this function [-Wmaybe-uninitialized]
    7 | class lca_t {
      |       ^~~~~

• 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