Submission #1263601

#TimeUsernameProblemLanguageResultExecution timeMemory
1263601kustov_vadim_533Cat Exercise (JOI23_ho_t4)C++20
31 / 100
2096 ms44356 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; #define len(v) (int)((v).size()) template<typename T> ostream& operator<<(ostream& out, const vector<T> &a){ for (auto& x : a){ out << x << ' '; } out << '\n'; return out; } template<typename T> istream& operator>>(istream& in, vector<T> &a){ for (size_t i = 0; i < a.size(); ++i){ in >> a[i]; } return in; } mt19937 gen; struct obj{ ll vl = -1e18, add = 0; int i = -1; obj() = default; obj(int i, int x) : vl(x), i(i) {} }; obj merge(obj &a, obj &b){ if (a.vl > b.vl){ return a; } else { return b; } } const int sz = 1 << 20; obj tree[sz]; void push(int v, int ln){ if (tree[v].add == 0) return; if (ln > 1){ tree[v * 2].add += tree[v].add; tree[v * 2 + 1].add += tree[v].add; } tree[v].vl += tree[v].add; tree[v].add = 0; } void upd(int v, int l, int r, int ql, int qr, int qx){ push(v, r - l); if (l >= qr || ql >= r) return; if (l >= ql && r <= qr) { tree[v].add += qx; push(v, r - l); return; } int m = (l + r) / 2; upd(v * 2, l, m, ql, qr, qx); upd(v * 2 + 1, m, r, ql, qr, qx); tree[v] = merge(tree[v * 2], tree[v * 2 + 1]); } obj sum(int v, int l, int r, int ql, int qr){ push(v, r - l); if (l >= qr || ql >= r) return obj(); if (l >= ql && r <= qr) tree[v]; int m = (l + r) / 2; obj r1 = sum(v * 2, l, m, ql, qr); obj r2 = sum(v * 2 + 1, m, r, ql, qr); return merge(r1, r2); } void build(int v, int l, int r, vector<int>& a){ if (r - l == 1){ tree[v] = obj(l, a[l]); return; } int m = (l + r) / 2; build(v * 2, l, m, a); build(v * 2 + 1, m, r, a); tree[v] = merge(tree[v * 2], tree[v * 2 + 1]); } const int N = 2e5 + 7; vector<int> g[N]; int a[N]; bool us[N]; int tim = 0; int tin[N], tout[N], p[N], h[N]; void dfs2(int v, int pre){ tin[v] = tim++; p[v] = pre; h[v] = h[pre] + 1; for (int u : g[v]){ if (u == pre) continue; dfs2(u, v); } tout[v] = tim; } const int LGN = 20; int up[LGN][N]; int la(int v, int k){ for (int j = LGN - 1; j >= 0; --j){ if (k >= (1 << j)){ k -= (1 << j); v = up[j][v]; } } return v; } int lca(int v, int u){ v = la(v, h[v] - h[u]); u = la(u, h[u] - h[v]); if (v == u) return v; for (int j = LGN - 1; j >= 0; --j){ if (up[j][v] != up[j][u]){ v = up[j][v]; u = up[j][u]; } } return up[0][v]; } int dist(int v, int u){ return h[v] + h[u] - 2 * h[lca(u, v)]; } pair<int, int> dfs3(int v, int p){ pair<int, int> res = {v, 0}; for (int u : g[v]){ if (u == p) continue; if (us[u]) continue; pair<int, int> r = dfs3(u, v); r.second++; if (a[r.first] > a[res.first]) res = r; } return res; } int dfs(int v){ pair<int, int> cf = dfs3(v, v); cf.second = dist(cf.first, v); v = cf.first; int res = 0; us[v] = true; for (int u : g[v]){ if (!us[u]){ res = max(res, dfs(u)); } } us[v] = false; return res + cf.second + 1; } inline void solve() { int n; cin >> n; for (int i = 0; i < n; ++i){ cin >> a[i]; us[i] = false; } for (int i = 0; i < n - 1; ++i){ int x, y; cin >> x >> y; g[--x].push_back(--y); g[y].push_back(x); } dfs2(0, 0); for (int i = 0; i < n; ++i){ up[0][i] = p[i]; } for (int j = 1; j < LGN; ++j){ for (int i = 0; i < n; ++i){ up[j][i] = up[j - 1][up[j - 1][i]]; } } vector<int> init(n); for (int i = 0; i < n; ++i){ init[tin[i]] = a[i]; } // build(1, 0, n, init); int ans = 0; for (int i = 0; i < n; ++i){ if (a[i] == n){ ans = dfs(i); } } cout << ans - 1 << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.precision(60); int t = 1; // cin >> t; while (t--) { 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...