Submission #1212457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212457		qilby	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	181 ms	61400 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 200009, L = 20;

vector < int > g[N], q[N];
ll n, h[N], w[N], f[N], s[N], lnk[N];
int tme, tin[N], tout[N], d[N], up[N][L];

int get(int v) { return (v == lnk[v] ? v : lnk[v] = get(lnk[v])); }

void unite(int u, int v) {
    u = get(u), v = get(v);
    if (u == v) return;
    lnk[u] = v;
    s[v] = max(s[v], s[u]);
}

void dfs(int v, int p, int len) {
    d[v] = len;
    tin[v] = ++tme;

    up[v][0] = p;
    for (int i = 1; i < L; i++) up[v][i] = up[up[v][i - 1]][i - 1];

    for (auto u : g[v]) if (u != p) dfs(u, v, len + 1);
    tout[v] = tme;
}

bool upper(int u, int v) { return tin[v] >= tin[u] && tout[v] <= tout[u]; }

int lca(int u, int v) {
    if (upper(u, v)) return u;
    for (int i = L - 1; i >= 0; i--) if (!upper(up[u][i], v)) u = up[u][i];
    return up[u][0];
}

int dist(int u, int v) { return d[u] + d[v] - 2 * d[lca(u, v)]; }

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

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        w[h[i]] = i;
    }

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 1, 0);

    for (int i = 1; i <= n; i++) lnk[i] = i;

    for (int i = 1; i <= n; i++) {
        int v = w[i];
        for (auto u : g[v]) q[s[get(u)]].push_back(i);
        s[v] = i;
        for (auto u : g[v]) if (h[u] < h[v]) unite(u, v);
    }

    for (int i = 1; i <= n; i++) {
        for (auto j : q[i]) f[j] = max(f[j], f[i] + dist(w[i], w[j]));
    }

    cout << f[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