제출 #1151146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151146		AlperenT_	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	283 ms	66328 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 = 5e5+20 , maxm = 2e4 + 220, sq = 500 , inf = 1e18+10 , lg = 20 , mod =998244353 ; 
int par[maxn] , p[maxn] , dp[maxn] , q[maxn] , dis[maxn] , jad[maxn][lg+2] ;
vector <int> G[maxn] ;
int lca(int v ,int u){
    if(dis[v] < dis[u])swap(v,u) ;
    int z = dis[v]-dis[u] ;
    rep(i , 0, lg){
        if(z>>i&1){
            v= jad[v][i] ;
        }
    }
    per(i , lg ,0){
        if(jad[v][i] != jad[u][i]){
            v = jad[v][i] ;
            u = jad[u][i] ;
        }
    }
    if(v==u)return v; 
    return jad[v][0] ;
}
int d(int v , int u ){
    return dis[v]+dis[u] - 2*dis[lca(v,u)] ;
}
int find(int v){
    if(par[v] == 0)return v;
    return par[v] = find(par[v]) ;
}
void mrg(int v , int u){
    v=find(v);u = find(u);
    dp[v]=max(dp[v] , dp[u]+d(v,u)) ;
    par[u] =v ;
}
void dfs(int v, int p =0 ){
    jad[v][0] = p ;
    rep(i ,1 ,lg){
        jad[v][i] = jad[jad[v][i-1]][i-1] ;
    }
     for(int u : G[v]){
        if(u == p)continue ; 
        dis[u] = dis[v] + 1; 
        dfs(u , 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) ;
    }
    dfs(1) ;
    rep(i ,1, n){
        for(int u : G[q[i]]){
            if(i > p[u]){
                mrg(q[i] , u) ;
            } 
        }
    }
    cout << dp[q[n]] << '\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