Submission #1151107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151107		AlperenT_	Cat Exercise (JOI23_ho_t4)	C++20	31 / 100	2100 ms	153668 KiB

Main

#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld long double
#define int long long 
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 6e6+20 , maxm = 2e4 + 220, sq = 500 , inf = 1e18+10 , mod =998244353 ; 
vector <int> G[maxn] ; 
int dp[maxn]  ,p[maxn] , q[maxn];

void dfs(int v , int r , int mx , int d ,int pa =0 ){
    if(p[v] > p[r])return ;
    if(p[v] >= mx){
        dp[r] = max(dp[r] , dp[v] + d); 
    }
    for(int u : G[v]){
        if(u == pa)continue ;
        dfs(u , r , max(mx , p[u]) , d+1 , v);
    }
}

signed main(){
    ios_base::sync_with_stdio(false) ; cin.tie(0) ;
    int n ;
    cin >> n ; 
    rep(i ,1, n){
        cin >> p[i] ;
        q[p[i]]= i ; 
    }
    rep(i , 1, n-1){
        int v, u ;
        cin >> v >> u ;
        G[v].pb(u);
        G[u].pb(v) ;
    }
    rep(i ,1, n){
        dfs(q[i] , q[i] , 0 , 0) ;
    }
    cout << dp[q[n]] << "\n"; 
}
/*
 
*/

• 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