oj.uz

답안 #930465

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
930465 2024-02-20T00:41:40 Z Darren0724 Cat Exercise (JOI23_ho_t4) C++17
0 / 100
 15 ms 29436 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
const int N=200005;
const int K=20;
vector<int> pa(N);
int Find(int k){
    return (pa[k]==k?k:pa[k]=Find(pa[k]));
}
void onion(int a,int b){
    a=Find(a),b=Find(b);
    if(a!=b)pa[a]=b;
}
int32_t main() {
    LCBorz;
    iota(all(pa),0);
    int n;cin>>n;
    vector<int> v(N),v1(N),dp(N),adj[N],dis(N);
    vector jump(K,vector(N,0));
    for(int i=1;i<=n;i++){
        cin>>v[i];
        v1[v[i]]=i;
    }
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    auto dfs=[&](auto dfs1,int k)->void {
        for(int i=1;i<K;i++){
            jump[i][k]=jump[i-1][jump[i-1][k]];
        }
        for(int j:adj[k]){
            if(j==jump[0][k])continue;
            jump[0][j]=k;
            dis[j]=dis[k]+1;
            dfs1(dfs1,j);
        }
    };
    auto lca=[&](int a,int b)->int {
        if(dis[a]<dis[b])swap(a,b);
        int d=dis[a]-dis[b];
        for(int i=K-1;i>=0;i--){
            if(d&(1<<i)){
                a=jump[i][a];
            }
        }
        if(a==b)return a;
        for(int i=K-1;i>=0;i--){
            if(jump[i][a]!=jump[i][b]){
                a=jump[i][a],b=jump[i][b];
            }
        }
        return jump[0][a];
    };
    auto far=[&](int a,int b){
        return dis[a]+dis[b]-2*dis[lca(a,b)];
    };
    jump[0][1]=1;
    dfs(dfs,1);
    for(int i1=1;i1<=n;i1++){
        int i=v1[i1];
        for(int j:adj[i]){
            if(v[j]>v[i])continue;
            int p=j;
            dp[i]=max(dp[i],dp[p]+far(i,p));
            onion(p,i);
        }
    }
    cout<<dp[v1[n]]<<endl;

    return 0;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 29272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 29272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 29272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 29272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 29272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 29436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 29272 KB Output isn't correct
2 Halted 0 ms 0 KB -