Submission #1190972

#TimeUsernameProblemLanguageResultExecution timeMemory
1190972M_W_13Cat Exercise (JOI23_ho_t4)C++20
100 / 100
149 ms41136 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (n); i++) typedef long long ll; #define pb push_back #define st first #define nd second const int MAXN = 2e5 + 7; const int MAXK = 19; int depth[MAXN]; int skok[MAXN][MAXK]; vector<int> g[MAXN]; int P[MAXN]; int ojc[MAXN]; ll ans[MAXN]; int find(int v) { int pom = v; while (ojc[pom] != pom) { pom = ojc[pom]; } while (ojc[v] != v) { int pam = ojc[v]; ojc[v] = pom; v = pam; } return v; } void dfs(int v, int last) { depth[v] = depth[last] + 1; skok[v][0] = last; for (int k = 1; k < MAXK; k++) { skok[v][k] = skok[skok[v][k - 1]][k - 1]; } for (auto syn: g[v]) { if (syn == last) continue; dfs(syn, v); } } int lca(int a, int b) { if (depth[a] > depth[b]) { swap(a, b); } int k = MAXK - 1; while (depth[a] < depth[b]) { if ((depth[b] - (1 << k)) < depth[a]) { } else { b = skok[b][k]; } k--; } if (a == b) { return a; } k = MAXK - 1; while (skok[a][0] != skok[b][0]) { if (skok[a][k] != skok[b][k]) { a = skok[a][k]; b = skok[b][k]; } k--; } return skok[a][0]; } void solve() { rep(i, MAXN) { ojc[i] = i; } int n; cin >> n; pair<int, int> T[n]; rep(i, n) { int p; cin >> p; P[i + 1] = p; T[i] = {p, i + 1}; } rep(i, n - 1) { int a, b; cin >> a >> b; g[a].pb(b); g[b].pb(a); } dfs(1, 1); sort(T, T + n); ll odp = 0; rep(i, n) { int v = T[i].nd; for (auto syn: g[v]) { if (P[syn] < P[v]) { int w = find(syn); ll odl = depth[w] + depth[v] - 2 * depth[lca(w, v)]; ans[v] = max(ans[v], odl + ans[w]); ojc[w] = v; } } odp = max(odp, ans[v]); } cout << odp << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }
#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...