Submission #1153260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153260		irmuun	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	171 ms	58360 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll N=2e5+5;

ll n;
ll h[N],p[N];
vector<ll>g[N];

struct dsu{
    ll n;
    vector<ll>sz,p,mx;
    dsu(ll n){
        sz.resize(n+1);
        fill(all(sz),1);
        p.resize(n+1);
        iota(all(p),0);
        mx.resize(n+1);
        iota(all(mx),0);//position of max
    }
    ll find(ll x){
        if(p[x]==x) return x;
        return p[x]=find(p[x]);
    }
    bool same(ll x,ll y){
        x=find(x);
        y=find(y);
        return x==y;
    }
    bool merge(ll x,ll y){
        x=find(x);
        y=find(y);
        if(x!=y){
            if(sz[x]<sz[y]) swap(x,y);
            p[y]=x;
            sz[x]+=sz[y];
            if(h[mx[x]]>h[mx[y]]){
                mx[x]=mx[x];
            }
            else{
                mx[x]=mx[y];
            }
            return true;
        }
        return false;
    }
    ll get(ll x){
        x=find(x);
        return mx[x];
    }
};

const ll lg=18;
ll dep[N],par[N][lg];

void dfs(ll x,ll pr){
    par[x][0]=pr;
    for(ll y:g[x]){
        if(y!=pr){
            dep[y]=dep[x]+1;
            dfs(y,x);
        }
    }
}
void calc(){
    for(ll j=1;j<lg;j++){
        for(ll i=1;i<=n;i++){
            par[i][j]=par[par[i][j-1]][j-1];
        }
    }
}
ll up(ll x,ll d){
    for(ll j=lg-1;j>=0;j--){
        if(d&(1ll<<j)){
            x=par[x][j];
        }
    }
    return x;
}
ll lca(ll x,ll y){
    if(dep[x]<dep[y]) swap(x,y);
    x=up(x,dep[x]-dep[y]);
    for(ll j=lg-1;j>=0;j--){
        if(par[x][j]!=par[y][j]){
            x=par[x][j];
            y=par[y][j];
        }
    }
    if(x!=y) x=par[x][0];
    return x;
}
ll dist(ll x,ll y){
    ll g=lca(x,y);
    return dep[x]+dep[y]-(dep[g]<<1);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>h[i];
        p[h[i]]=i;
    }
    dsu ds(n);
    for(ll i=1;i<n;i++){
        ll a,b;
        cin>>a>>b;
        g[a].pb(b);
        g[b].pb(a);
    }
    dfs(1,1);
    calc();
    ll dp[n+5];
    fill(dp,dp+n+1,0);
    for(ll i=1;i<=n;i++){
        for(ll j:g[p[i]]){
            if(h[j]<h[p[i]]){
                ll pos=ds.get(j);
                dp[i]=max(dp[i],dp[h[pos]]+dist(p[i],pos));
                ds.merge(p[i],j);
            }
        }
    }
    cout<<dp[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