Submission #987661

#TimeUsernameProblemLanguageResultExecution timeMemory
987661OtalpCat Exercise (JOI23_ho_t4)C++14
31 / 100
2050 ms24180 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define ll long long vector<int> q[200100]; int p[200100], sz[200100]; ll mx[200100]; ll dp[200100]; int jmp[200100][30]; int tin[200100], tout[200100], timer = 0; int h[200100]; int pos[200100]; int a[200100]; int get(int a){ if(p[a] == a) return a; return p[a] = get(p[a]); } void un(int x, int y){ x = get(x); y = get(y); if(x == y) return; if(sz[x] > sz[y]) swap(x, y); p[y] = p[x]; sz[x] += sz[y]; if(a[mx[x]] < a[mx[y]]) mx[x] = mx[y]; } ll dfs(int v, int p, int k, int h){ ll res = dp[v] + k; for(int to: q[v]){ if(to == p or a[to] > a[h]) continue; res = max(dfs(to, v, k + 1, h), res); } return res; } void solve(){ int n; cin>>n; for(int i=1; i<=n; i++){ cin>>a[i]; p[i] = i; mx[i] = i; pos[a[i]] = i; sz[i] = 1; dp[i] = 0; } for(int i=1; i<n; i++){ int l, r; cin>>l>>r; q[l].pb(r); q[r].pb(l); } for(int i=1; i<=n; i++){ vector<int> d; int v = pos[i]; dp[v] = dfs(v, 0, 0, v); } cout<<dp[pos[n]]<<'\n'; } int main(){ solve(); }
#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...