Submission #894207

#	Time	Username	Problem	Language	Result	Execution time	Memory
894207		box	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	276 ms	45652 KiB

Main

#include "bits/stdc++.h"

using namespace std;

const int N = 2e5, L = 18;

#ifndef LOCAL
#define cerr if (0) cerr
#endif

int n, p[N];
int pp[L][N], d[N];
vector <int> g[N];
long long dp[N];
int f[N];

int uf(int i) {
    return f[i] == i ? i : f[i] = uf(f[i]);
}

void dfs(int i) {
    for (int l = 1; l < L; l++) pp[l][i] = pp[l - 1][pp[l - 1][i]];
    for (int j: g[i])
        if (pp[0][i] != j) {
            pp[0][j] = i;
            d[j] = d[i] + 1;
            dfs(j);
        }
}
int lca(int i, int j) {
    if (d[i] < d[j]) swap(i, j);
    int k = d[i] - d[j];
    for (int l = 0; l < L; l++)
        if (k >> l & 1) i = pp[l][i];
    if (i == j) return i;
    for (int l = L - 1; l >= 0; l--)
        if (pp[l][i] != pp[l][j]) i = pp[l][i], j = pp[l][j];
    return pp[0][i];
}
int dis(int i, int j) {
    return d[i] + d[j] - 2 * d[lca(i, j)];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> p[i], p[i]--;
    for (int h = 0; h < n - 1; h++) {
        int i, j;
        cin >> i >> j, i--, j--;
        i = p[i], j = p[j];
        cerr << "edge " << i << " " << j << endl;
        g[i].push_back(j);
        g[j].push_back(i);
    }
    pp[0][0] = 0;
    dfs(0);
    for (int i = 0; i < n; i++) f[i] = i;
    for (int i = 0; i < n; i++) {
        for (int j: g[i])
            if (j < i) {
                int c = uf(j);
                cerr << c << " " << i << "|" << dis(c, i) << endl;
                dp[i] = max(dp[i], dp[c] + dis(c, i));
                f[c] = i;
            }
        cerr << "dp[" << i << "]=" << dp[i] << endl;
    }
    cout << * max_element(dp, dp + n) << '\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