제출 #1261516

#제출 시각아이디문제언어결과실행 시간메모리
1261516vlomaczkCat Exercise (JOI23_ho_t4)C++20
0 / 100
18 ms30276 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; int M = 200'010; int maxlog = 17; vector<vector<pair<int, int>>> g(M); vector<int> p(M), h(M), depth(M); vector<vector<int>> jump(M, vector<int>(maxlog+1)); vector<int> rep(M, 0), sajz(M, 1), maks(M, 0); vector<vector<pair<int, int>>> rep_changes, sajz_changes, maks_changes; vector<bool> turned_on(M, 0); void mw_dfs(int v, int p, int a) { rep_changes.back().push_back({v, rep[v]}); rep[v] = a; for(auto[u, k] : g[v]) if(u!=p && turned_on[k]) mw_dfs(u, v, a); } void Union(int a, int b) { a = rep[a]; b = rep[b]; if(a==b) return; if(sajz[b] > sajz[a]) swap(a, b); rep_changes.push_back({}); sajz_changes.push_back({{a, sajz[a]}, {b, sajz[b]}}); maks_changes.push_back({{a, maks[a]}, {b, maks[b]}}); mw_dfs(b, 0, a); sajz[a] += sajz[b]; maks[a] = max(maks[a], maks[b]); } void rollback() { for(auto[a, b] : rep_changes.back()) rep[a] = b; for(auto[a, b] : sajz_changes.back()) sajz[a] = b; for(auto[a, b] : maks_changes.back()) maks[a] = b; rep_changes.pop_back(); sajz_changes.pop_back(); maks_changes.pop_back(); } void jump_dfs(int v, int p) { depth[v] = depth[p] + 1; jump[v][0] = p; for(int i=1; i<=maxlog; ++i) jump[v][i] = jump[jump[v][i-1]][i-1]; for(auto[u, k] : g[v]) if(u!=p) jump_dfs(u, v); } int lca(int a, int b) { if(depth[b] > depth[a]) swap(a, b); for(int i=maxlog; i>=0; --i) { if(depth[jump[a][i]] >= depth[b]) a = jump[a][i]; } if(a==b) return a; for(int i=maxlog; i>=0; --i) { if(jump[a][i]!=jump[b][i]) { a = jump[a][i]; b = jump[b][i]; } } return jump[a][0]; } int dist(int a, int b) { return depth[a] + depth[b] - 2*depth[lca(a, b)]; } int ans(int v) { int odp = 0; for(auto[u, k] : g[v]) { if(turned_on[k]) rollback(); } vector<int> nexts; for(auto[u, k] : g[v]) { if(turned_on[k]) { turned_on[k] = 0; nexts.push_back(maks[rep[u]]); } } sort(nexts.begin(), nexts.end()); reverse(nexts.begin(), nexts.end()); for(auto u : nexts) odp = max(odp, dist(p[u], v)+ans(p[u])); return odp; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for(int i=1; i<=n; ++i) { cin >> h[i]; p[h[i]] = i; } for(int i=1; i<n; ++i) { int a, b; cin >> a >> b; g[a].push_back({b, i}); g[b].push_back({a, i}); } for(int i=1; i<=n; ++i) rep[i] = i; for(int i=1; i<=n; ++i) maks[i] = h[i]; for(int i=1; i<=n; ++i) { int v = p[i]; for(auto[u, k] : g[v]) { if(h[u] > h[v] || turned_on[k]) continue; Union(v, u); turned_on[k] = 1; } } jump_dfs(1, 0); cout << ans(p[n]) << "\n"; 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...