제출 #1095405

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1095405		giaminh2211	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	178 ms	51836 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll=long long;

const int N=2e5+13;
int n;
int a[N];
int h[N];
int d[N];
vector<int> g[N];
int x, y;
int par[N];
int st[N][20];
int val[N];
ll dp[N];

void dfs(int v, int par){
    for(int c: g[v]){
        if(c==par) continue;
        d[c]=d[v]+1;
        st[c][0]=v;
        for(int j=1; j<20; j++){
            st[c][j]=st[st[c][j-1]][j-1];
        }
        dfs(c, v);
    }
}

void scan(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        h[a[i]]=i;
        val[i]=a[i];
        par[i]=i;
    }
    for(int i=1; i<n; i++){
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1, 1);
}

int lca(int u, int v){
    if(d[u] > d[v]) swap(u, v);
    int k=d[v]-d[u];
    for(int j=0; j<=19; j++){
        if(k >> j & 1){
            v=st[v][j];
        }
    }
    if(u==v) return u;
    for(int j=19; j>=0; j--){
        if(st[u][j]!=st[v][j]){
            u=st[u][j];
            v=st[v][j];
        }
    }
    return st[u][0];
}

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

int f(int v){
    if(par[v]==v) return v;
    par[v]=f(par[v]);
    return par[v];
}

void uni(int u, int v){
    int Ru=f(u);
    int Rv=f(v);
    if(Ru!=Rv){
        if(val[Ru] > val[Rv]) swap(Ru, Rv); // Ru < Rv
        par[Ru]=Rv;
        val[Rv]=max(val[Ru], val[Rv]);
    }
}

void solve(){
    for(int i=1; i<=n; i++){
        int u=h[i];
        for(int v: g[u]){
            if(a[v] < a[u]){
                int prv=f(v);
                dp[u]=max(dp[u], dp[prv] + dis(prv, u));
                uni(u, v);
            }
        }
    }
    cout << dp[h[n]];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    scan();
    solve();
}

• 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