Submission #930464

#	Time	Username	Problem	Language	Result	Execution time	Memory
930464		Darren0724	Cat Exercise (JOI23_ho_t4)	C++17	54 / 100	198 ms	39276 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#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;
            dp[i]=max(dp[i],dp[Find(j)]+far(i,Find(j)));
            onion(Find(j),i);
        }
    }
    cout<<dp[v1[n]]<<endl;

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 23 / 23
• Subtask 7: 0 / 26