Submission #1262531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262531		nguyn	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	108 ms	45596 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

const int N = 2e5 + 5;

int n;
int p[N];
vector<int> g[N];

int mx[N], lab[N];
int h[N];
int up[N][18];
ll f[N];

void dfs(int u, int p) {
    for (int v : g[u]) {
        if (v == p) continue;
        h[v] = h[u] + 1;
        up[v][0] = u;
        for (int i = 1; i < 18; i++) {
            up[v][i] = up[up[v][i - 1]][i - 1];
        }
        dfs(v, u);
    }
}

int lca(int u, int v) {
    if (h[v] != h[u]) {
        if (h[u] < h[v]) swap(u, v);
        int k = h[u] - h[v];
        for (int i = 0; (1 << i) <= k; i++) {
            if (k >> i & 1) {
                u = up[u][i];
            }
        }
    }
    if (u == v) return u;
    for (int i = 17; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

int find(int u) {
    return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}

void join(int u, int v) {
    if ((u = find(u)) == (v = find(v))) return;
    if (lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    mx[u] = max(mx[u], mx[v]);
    lab[v] = u;
}

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

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        mx[i] = i; lab[i] = -1;
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u = p[u];
        v = p[v];
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j : g[i]) {
            int v = mx[find(j)];
            if (v < i) {
                join(i, v);
                f[i] = max(f[i], f[v] + dist(i, v));
            }
        }
    }
    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