Submission #1032329

#TimeUsernameProblemLanguageResultExecution timeMemory
1032329vjudge1Cat Exercise (JOI23_ho_t4)C++17
100 / 100
178 ms66644 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define for1(i,j,k) for(int i=(j);i<=(k);i++) #define for2(i,j,k) for(int i=(j);i>=(k);i--) #define for3(i,j,k,l) for(int i=j;i<=k;i+=l) #define bit(n,i) ((n>>i)&1) #define all(x) x.begin(),x.end() //#pragma GCC optimize("O2,unroll-loops") //#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt") #define int long long typedef long long ll; typedef pair<int,int> pii; typedef long double ld; typedef pair<ld,ld> pdd; typedef pair<ll,ll> pll; const ll maxn=2e5+69; const ll offset=1e9; const ll block_sz=317; const ll inf=1e18; const ll mod=123456789; int n,p[maxn],par[maxn]; vector<int> adj[maxn]; int Find(int u) { return par[u]<0?u:par[u]=Find(par[u]); } int dep[maxn],up[maxn][21],in[maxn],out[maxn],Time,dp[maxn]; void dfs(int u,int pre) { in[u]=++Time; up[u][0]=pre; for1(i,1,20) up[u][i]=up[up[u][i-1]][i-1]; for(int v:adj[u]) { if (v==pre) continue; dep[v]=dep[u]+1; dfs(v,u); } out[u]=Time; } bool is_ancestor(int u,int v) { return in[u]<=in[v] && out[v]<=out[u]; } int lca(int u,int v) { if (is_ancestor(u,v)) return u; if (is_ancestor(v,u)) return v; for2(i,20,0) if (!is_ancestor(up[u][i],v)) u=up[u][i]; return up[u][0]; } void sol() { cin >> n; for1(i,1,n) cin >> p[i]; for1(i,1,n-1) { int u,v; cin>> u>> v; u=p[u],v=p[v]; adj[u].pb(v); adj[v].pb(u); } dfs(1,1); for1(i,1,n) par[i]=-1; for1(u,1,n) { for(int v:adj[u]) { v=Find(v); if (v<u) { par[v]=u; dp[u]=max(dp[u],dp[v]+dep[u]+dep[v]-2*dep[lca(u,v)]); } } } cout << dp[n]; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen("PAINT.inp","r",stdin); // freopen("PAINT.out","w",stdout); int t=1;//cin >> t; while (t--) { sol(); } } /* */
#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...