Submission #1195321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195321		Newtonabc	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	287 ms	63132 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int p[N],pa[N],dp[N][20],d[N],dpb[N];
vector<int> adj[N];
bool cp(int a,int b){
    return p[a]<p[b];
}
void dfs(int u,int p){
    for(auto v:adj[u]){
        if(v==p) continue;
        dp[v][0]=u;
        d[v]=d[u]+1;
        dfs(v,u);
    }
}
int lca(int a,int b){
    //make same depth (put b up)
    if(d[b]<d[a]) swap(a,b);
    for(int i=19;i>=0;i--) if(d[dp[b][i]]>=d[a]) b=dp[b][i];
    if(a==b) return a;
    for(int i=19;i>=0;i--) if(dp[b][i]!=dp[a][i]) a=dp[a][i],b=dp[b][i];
    return dp[a][0];
}
int path(int a,int b){
    return d[a]+d[b]-2*d[lca(a,b)];
}
int root(int x){
    if(pa[x]==x) return x;
    return pa[x]=root(pa[x]);
}
void merge(int a,int b){
    int ra=root(a),rb=root(b);
    if(ra==rb) return;
    //root is the node that has maximum height
    if(p[ra]>p[rb]) pa[rb]=ra;
    else pa[ra]=rb;
}
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) pa[i]=i;
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u >>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> sp;
    for(int i=1;i<=n;i++) sp.push_back(i);
    sort(sp.begin(),sp.end(),cp);
    dfs(sp.back(),-1);
    dp[sp.back()][0]=sp.back();
    for(int i=1;i<20;i++) for(int j=1;j<=n;j++) dp[j][i]=dp[dp[j][i-1]][i-1];
    for(auto u:sp){
        for(auto v:adj[u]){
            if(p[v]>p[u]) continue;
            //cout<<u <<" " <<v <<" " <<dpb[u] <<" " <<dpb[v]+path(u,root(v)) <<"\n";
            //cout<<root(u) <<" " <<root(v) <<"\n";
            dpb[u]=max(dpb[u],dpb[root(v)]+path(u,root(v)));
            merge(u,v);
            //cout<<root(u) <<" " <<root(v) <<"\n";
        }
    }
    cout<<dpb[sp.back()];
}

• 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