Submission #1094914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094914		Nom_mxmx	Cat Exercise (JOI23_ho_t4)	C++14	31 / 100	153 ms	85280 KiB

Main

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

#define nl '\n'
#define pb push_back

const int N = 2e5;
vector<int> g[N];
int w[N];
int p[N];
int d[N];
int rep[N];
int mx[N];
int dp[N];
int jmp[N][20];

int Find(int a) {
    return (rep[a] == a)? a : rep[a] = Find(rep[a]);
}

void Union(int a, int b) {
    a = Find(a), b = Find(b);
    rep[b] = a;
}

void dfs(int v, int p) {
    d[v] = d[p]+1;
    jmp[v][0] = p;

    for(int i=1; i<20; i++)
        jmp[v][i] = jmp[jmp[v][i-1]][i-1];

    for(auto u:g[v]) {
        if(u == p) continue;
        dfs(u, v);
    }
}

int lca(int a, int b) {
    if(d[a] < d[b]) swap(a, b);

    for(int i=19; i>=0; i--) {
        if(d[jmp[a][i]] >= d[b])
            a = jmp[a][i];
    }
    for(int i=19; i>=0; i--) {
        if(jmp[a][i] != jmp[b][i]) {
            a = jmp[a][i];
            b = jmp[b][i];
        }
    }
    if(a == b) return a;
    return jmp[a][0];
}

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

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

    int n;
    cin >> n;

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

    for(int i=1; i<n; i++) {
        int a, b;
        cin >> a >> b;

        g[a].pb(b);
        g[b].pb(a);
    }

    dfs(1, 0);
    for(int i=1; i<=n; i++) {
        int v = p[i];

        for(auto u:g[v]) {
            if(w[v] > w[u]) {
                int a = Find(u);

                dp[v] = max(dp[v], dp[a] + dist(v, a));
                Union(v, a); // v > a 
            }
        }
    }

    cout << dp[p[n]];
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26