Submission #1153128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153128		irmuun	Cat Exercise (JOI23_ho_t4)	C++20	31 / 100	2093 ms	21480 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,h[N],p[N];
vector<ll>g[N];

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;
    }
    for(ll i=1;i<n;i++){
        ll a,b;
        cin>>a>>b;
        g[a].pb(b);
        g[b].pb(a);
    }
    ll dp[n+5];
    fill(dp,dp+n+1,-1);
    dp[n]=0;
    vector<ll>b(n+5,1e9),dist(n+5,0);
    for(ll i=n;i>=1;i--){
        queue<ll>q;
        fill(all(b),1e9);
        b[i]=0;
        dist[i]=0;
        q.push(i);
        while(!q.empty()){
            ll x=q.front();
            q.pop();
            for(ll y:g[p[x]]){
                y=h[y];
                if(b[y]==1e9){
                    b[y]=max(y,b[x]);
                    dist[y]=dist[x]+1;
                    q.push(y);
                }
            }
        }
        if(dp[i]==-1) continue;
        for(ll j=i-1;j>=1;j--){
            if(b[j]==j){
                dp[j]=max(dp[j],dp[i]+dist[j]);
            }
        }
    }
    ll ans=0;
    for(ll i=1;i<=n;i++){
        ans=max(ans,dp[i]);
    }
    cout<<ans;
}

• 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