제출 #1246544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246544		nasjes	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	306 ms	114768 KiB

Main

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 1e6+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e17 + 77;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, m;
pll h[dim];
vll a[dim];
ll dp[dim], dep[dim], tin[dim], tout[dim];
ll jump[24][dim];
vll g[dim];
ll boss[dim];
ll findboss(ll v){
    if(boss[v]==v)return v;
    return boss[v]=findboss(boss[v]);
}
ll t=0;
void dfs(ll v,ll p,  ll d){
    dep[v]=d;
    t++;
    tin[v]=t;
    jump[0][v]=p;
    for(int i=1; i<=21; i++){
        jump[i][v]=jump[i-1][jump[i-1][v]];
    }
    for( auto x:a[v]){
        if(x==p)continue;
        dfs(x, v, d+1);
    }
    t++;
    tout[v]=t;
}
ll same(ll x, ll y){
    if(tin[x]<=tin[y] && tout[y]<=tout[x])return 1;
    swap(x, y);
    if(tin[x]<=tin[y] && tout[y]<=tout[x])return 1;
    return 0;
}
ll lca(ll x, ll y){
    if(dep[x]>dep[y])swap(x, y);
    ll cur=x;
    if(same(x, y)){
        return x;
    }
    for(int st=20; st>=0; st--){
        if(!same(jump[st][cur], y)){
            cur=jump[st][cur];
        }
    }
   // cout<<cur<<endl;
    return jump[0][cur];
}
ll dst(ll x, ll y){
    ll p1=dep[lca(x, y)];
    return dep[x]+dep[y]-2*p1;

}
void unite(ll x, ll y){
    ll xx=findboss(x);
    boss[xx]=y;
}
int main() {

    ll k, u, v;
    string s;
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>h[i].fi;
        h[i].se=i;
        dp[i]=0;
        boss[i]=i;
    }
    for(int i=1; i<=n-1; i++){
        cin>>u>>v;
        a[u].pb(v);
        a[v].pb(u);
        if(h[u]<h[v])swap(u, v);
        g[u].pb(v);
    }
    sort(h+1, h+1+n);
    t=0;
    dfs(1, 1, 1);
    for(int i=1; i<=n; i++){
        ll cur=h[i].se;
      // cout<<cur<<" -- ";
        for(auto x:g[cur]){
            ll tmp=findboss(x);
            ll d=dst(cur, tmp);
            //cout<<tmp<<" "<<d<<endl;
            dp[cur]=max(dp[cur], dp[tmp]+d);
        }
       // cout<<dp[cur]<<endl;
        for(auto x:g[cur]){
            unite(x, cur);
        }
    }
    cout<<dp[h[n].se]<<endl;
    return 0;
}

• 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