Submission #935703

#TimeUsernameProblemLanguageResultExecution timeMemory
935703carriewangCat Exercise (JOI23_ho_t4)C++17
100 / 100
323 ms55896 KiB
#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"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...