Submission #935703

#	Time	Username	Problem	Language	Result	Execution time	Memory
935703		carriewang	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	323 ms	55896 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) x.size()
#define all(x) x.begin(),x.end()
#define F first
#define S second
using namespace std;
const int maxn=200005;
int n,a,b,p[maxn][25],h[maxn];
ll dep[maxn],dp[maxn];
vi g[maxn];
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n;
    for(int i=0;i<n;i++) cin >> h[i];
    for(int i=1;i<n;i++){
        cin >>  a >> b;
        a--,b--;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    function<void(int,int)> dfs=[&](int x,int pre){
        dep[x]=dep[pre]+1;
        p[x][0]=pre;
        for(int i=1;i<25;i++) p[x][i]=p[p[x][i-1]][i-1];
        for(int u:g[x]){
            if(u==pre) continue;
            dfs(u,x);
        }
    };
    dfs(0,0);
    function<int(int,int)> lca=[&](int x,int y){
        if(dep[x]>dep[y]) swap(x,y);
        int tmp=dep[y]-dep[x],i=0;
        while(tmp){
            if(tmp&1) y=p[y][i];
            i++,tmp>>=1;
        }
        if(x==y) return x;
        for(int j=24;j>=0;j--){
            if(p[x][j]!=p[y][j]){
                x=p[x][j];
                y=p[y][j];
            }
        }
        return p[x][0];
    };
    vi ord(n),pa(n);
    iota(all(ord),0);
    iota(all(pa),0);
    sort(all(ord),[](int i,int j){return h[i]<h[j];});
    function<int(int)> get=[&](int x){
        return x==pa[x] ? x : pa[x]=get(pa[x]);
    };
    function<ll(int,int)> get_dist=[&](int x,int y){
        return dep[x]+dep[y]-2*dep[lca(x,y)];
    };
    for(int i:ord){
        for(int j:g[i]){
            if(h[i]>h[j]){
                dp[i]=max(dp[i],dp[get(j)]+get_dist(i,get(j)));
                pa[get(j)]=i;
            }
        }
    }
    cout << dp[ord[n-1]] << "\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