Submission #881699

#TimeUsernameProblemLanguageResultExecution timeMemory
881699AlcabelCat Exercise (JOI23_ho_t4)C++17
54 / 100
1334 ms201740 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 2e5, maxlog = 18, inf = 1e9; int a[maxn]; vector<int> g[maxn]; int sz[maxn], level[maxn], centPar[maxn][maxlog]; int dist[maxn][maxlog], mx[maxn][maxlog], idxNxt[maxn][maxlog]; vector<int> toutList; void dfsSz(int v, int p) { sz[v] = 1; for (const int& u : g[v]) { if (u != p && level[u] == -1) { dfsSz(u, v); sz[v] += sz[u]; } } toutList.emplace_back(v); } void dfsCalc(int v, int p, int j) { int i = 0; for (const int& u : g[v]) { if (u != p && level[u] == -1) { dist[u][j] = dist[v][j] + 1; mx[u][j] = max(mx[v][j], a[u]); centPar[u][j] = centPar[v][j]; if (p != -1) { idxNxt[u][j] = idxNxt[v][j]; } else { idxNxt[u][j] = i; } dfsCalc(u, v, j); } ++i; } } void findCentroid(int v, int j) { toutList.clear(); dfsSz(v, -1); for (const int& c : toutList) { if (2 * sz[c] >= sz[v]) { v = c; break; } } // cerr << "j: " << j << ", v: " << v << '\n'; level[v] = j; dist[v][j] = 0; mx[v][j] = a[v]; centPar[v][j] = v; dfsCalc(v, -1, j); for (const int& u : g[v]) { if (level[u] == -1) { findCentroid(u, j + 1); } } } struct SegTree { int n, N; vector<int> st; SegTree() {} SegTree(int _n) { n = _n; N = 1; while (N < n) { N <<= 1; } st.resize(2 * N, -inf); } void maxEq(int i, int x) { int v = N + i; st[v] = max(st[v], x); v >>= 1; while (v > 0) { st[v] = max(st[2 * v], st[2 * v + 1]); v >>= 1; } } int getMax(int l, int r) { int vl = N + l, vr = N + r; int res = -inf; while (vl < vr) { if (vl & 1) { res = max(res, st[vl]); } if ((vr ^ 1) & 1) { res = max(res, st[vr]); } vl = (vl + 1) >> 1; vr = (vr - 1) >> 1; } if (vl == vr) { res = max(res, st[vl]); } return res; } ~SegTree() {} }; SegTree st[maxn]; void solve() { int n; cin >> n; vector<int> posOf(n); for (int i = 0; i < n; ++i) { cin >> a[i]; --a[i]; posOf[a[i]] = i; level[i] = -1; } for (int i = 0; i < n - 1; ++i) { int v, u; cin >> v >> u; --v, --u; g[v].emplace_back(u); g[u].emplace_back(v); } for (int v = 0; v < n; ++v) { st[v] = SegTree(g[v].size()); } findCentroid(0, 0); vector<int> dp(n); set<tuple<int, int, int>> s; for (int i = 0; i < n; ++i) { while (!s.empty() && get<0>(*s.begin()) <= i) { int v = get<1>(*s.begin()), j = get<2>(*s.begin()); s.erase(s.begin()); st[centPar[v][j]].maxEq(idxNxt[v][j], dp[a[v]] + dist[v][j]); } int v = posOf[i]; for (int j = level[v]; j >= 0; --j) { if (mx[v][j] <= i) { int u = centPar[v][j]; int val; if (j < level[v]) { val = max(st[u].getMax(0, idxNxt[v][j] - 1), st[u].getMax(idxNxt[v][j] + 1, (int)g[u].size() - 1)); val = max(val, dp[a[u]]); } else { val = max(val, st[u].getMax(0, (int)g[u].size() - 1)); } dp[i] = max(dp[i], val + dist[v][j]); } } // cerr << "i: " << i << ", dp: " << dp[i] << '\n'; for (int j = level[v] - 1; j >= 0; --j) { s.emplace(mx[v][j], v, j); } } cout << dp[n - 1] << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); int T = 1; cin >> T; while (T--) { solve(); cerr << "-----------\n"; cout << "-----------\n"; } #else int T = 1; // cin >> T; while (T--) { solve(); } #endif return 0; }

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:139:21: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
  139 |                 int val;
      |                     ^~~
#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...