제출 #828673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
828673		lukameladze	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	376 ms	49476 KiB

Main

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long 
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5;
int n, a[N], lv[N], par[N][20],tin, in[N], out[N], p[N], mx[N], inv[N];
vector <int> v[N];
ll dp[N];
void dfs(int a, int p) {
    par[a][0] = p;
    in[a] = ++tin;
    lv[a] = lv[p] + 1;
    for (int i = 1; i <= 18; i++) {
        par[a][i] = par[par[a][i - 1]][i - 1];
    }
    for (int to : v[a]) {
        if (to == p) continue;
        dfs(to, a);
    }
    out[a] = ++tin;
}
int upper(int a, int b) {
    return (in[a] <= in[b] && out[a] >= out[b]);
}
int lca(int a, int b) {
    if (upper(a, b)) return a;
    for (int i = 18; i >= 0; i--) {
        if (par[a][i] && !upper(par[a][i], b)) a = par[a][i];
    }
    return par[a][0];
}
int dist(int a, int b) {
    return lv[a] + lv[b] - 2 * lv[lca(a, b)];
}
int get_col(int a) {
    if (a == p[a]) return a;
    else return p[a] = get_col(p[a]);
}
void col(int a, int b) {
    a = get_col(a);
    b = get_col(b);
    if (a == b) return ;
    p[b] = a;
    mx[a] = max(mx[a], mx[b]);
}
void init() {
    for (int i = 1; i <= n ;i++) {
        p[i] = i;
        mx[i] = a[i];
    }
}
signed main() {
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>a[i];
        inv[a[i]] = i;
    }
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }
    init();
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        int vert = inv[i];
        for (int to : v[vert]) {
            if (a[to] > i) continue;
            int nxt_vert = get_col(to); // maximum in the "subtree"
            
            dp[vert] = max(dp[vert], dp[nxt_vert] + dist(nxt_vert, vert));
            // cout<<vert <<" -- > "<<to<<"   "<<nxt_vert<<" "<<dist(nxt_vert, vert)<<" "<<dp[vert]<<"\n";
        }
        for (int to : v[vert]) {
            if (a[to] > i) continue;
            col(vert, to);
        }
    }
    cout<<dp[inv[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