Submission #1212444

#TimeUsernameProblemLanguageResultExecution timeMemory
1212444qilbyCat Exercise (JOI23_ho_t4)C++20
41 / 100
84 ms30908 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 200009; vector < int > g[N], q[N]; ll n, h[N], w[N], f[N], s[N], lnk[N]; int get(int v) { return (v == lnk[v] ? v : lnk[v] = get(lnk[v])); } void unite(int u, int v) { u = get(u), v = get(v); if (u == v) return; lnk[u] = v; s[v] = max(s[v], s[u]); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> h[i]; w[h[i]] = i; } for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } for (int i = 1; i <= n; i++) lnk[i] = i; for (int i = 1; i <= n; i++) { int v = w[i]; for (auto u : g[v]) q[s[get(u)]].push_back(h[v]); s[v] = h[v]; for (auto u : g[v]) if (h[u] < h[v]) unite(u, v); } for (int i = 1; i <= n; i++) { for (auto j : q[i]) f[j] = max(f[j], f[i] + abs(w[i] - w[j])); } cout << f[n]; }
#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...