Submission #895150

#	Time	Username	Problem	Language	Result	Execution time	Memory
895150		hmm789	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	218 ms	58968 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 998244353

vector<int> adj[200000];
int p[200000][18], depth[200000], dp[200000], pa[200000];

int root(int x) {
    if(pa[x] == x) return x;
    else return pa[x] = root(pa[x]);
}

void merge(int x, int y) {
    x = root(x); y = root(y);
    if(x == y) return;
    if(x > y) swap(x, y);
    pa[x] = y;
}

void dfs(int x, int par, int d) {
    depth[x] = d;
    p[x][0] = par;
    for(int i = 1; i < 18; i++) {
        if(p[x][i-1] == -1) break;
        p[x][i] = p[p[x][i-1]][i-1];
    }
    for(int i : adj[x]) if(i != par) dfs(i, x, d+1);
}

int lca(int x, int y) {
    if(depth[x] < depth[y]) swap(x, y);
    int h = depth[x]-depth[y];
    for(int i = 0; i < 18; i++) {
        if(h&(1<<i)) x = p[x][i];
    }
    if(x == y) return x;
    for(int i = 17; i >= 0; i--) {
        if(p[x][i] != p[y][i]) {
            x = p[x][i]; y = p[y][i];
        }
    }
    return p[x][0];
}

int dist(int x, int y) {
    return depth[x]+depth[y]-2*depth[lca(x, y)];
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, x, y;
    cin >> n;
    int p[n];
    for(int i = 0; i < n; i++) {
        cin >> p[i];
        p[i]--;
    }
    for(int i = 0; i < n-1; i++) {
        cin >> x >> y;
        x--; y--;
        adj[p[x]].push_back(p[y]);
        adj[p[y]].push_back(p[x]);
    }
    memset(p, -1, sizeof(p));
    for(int i = 0; i < n; i++) pa[i] = i;
    dfs(0, -1, 0);
    for(int i = 0; i < n; i++) {
        for(int j : adj[i]) if(j < i) {
            int rt = root(j);
            dp[i] = max(dp[i], dp[rt]+dist(rt, i));
            merge(i, j);
        }
    }
    cout << dp[n-1];
}

• 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