Submission #525865

#TimeUsernameProblemLanguageResultExecution timeMemory
525865mjhmjh1104Mountains and Valleys (CCO20_day1problem3)C++17
3 / 25
835 ms29196 KiB
#include <set> #include <cstdio> #include <vector> #include <utility> #include <iterator> #include <algorithm> using namespace std; int n, m; vector<int> tree[200006], child[200006]; vector<pair<int, int>> adj[200006]; int _par[200006], _sz[200006]; int sz[200006], depth[200006], par[200006]; int in[200006], top[100006], T; int sp[18][200006]; multiset<int> lt_depth[200006]; int max_depth[200006], rev_max_depth[200006], dist[200006], rev_dist[200006]; int edge[200006]; int dfs(int x, int prev = -1) { _par[x] = prev; _sz[x] = 1; for (auto &i: tree[x]) if (i != prev) { _sz[x] = max(_sz[x], dfs(i, x) + 1); } return _sz[x]; } int dfs_dist(int x) { vector<int> v; max_depth[x] = 0; dist[x] = 0; for (auto &i: child[x]) { v.push_back(dfs_dist(i) + 1); max_depth[x] = max(max_depth[x], v.back()); dist[x] = max(dist[x], dist[i]); } int v0 = max_element(v.begin(), v.end()) - v.begin(); int X = v[v0]; if (!v.empty()) v[v0] = 0; int v1 = max_element(v.begin(), v.end()) - v.begin(); v[v0] = X; if (!v.empty()) dist[x] = max(dist[x], v[v0]); if ((int)v.size() > 1) dist[x] = max(dist[x], v[v0] + v[v1]); return max_depth[x]; } void dfs_rev_dist(int x) { multiset<int> v, u, w; if (par[x] != -1) { v.insert(rev_max_depth[x]); u.insert(rev_dist[x]); } for (auto &i: child[x]) { v.insert(max_depth[i] + 1); u.insert(dist[i]); } for (auto &i: child[x]) { v.erase(v.find(max_depth[i] + 1)); u.erase(u.find(dist[i])); if (!u.empty()) rev_dist[i] = *u.rbegin(); if (!v.empty()) rev_dist[i] = max(rev_dist[i], rev_max_depth[i] = *v.rbegin() + 1); if ((int)v.size() > 1) rev_dist[i] = max(rev_dist[i], *v.rbegin() + *prev(prev(v.end()))); v.insert(max_depth[i] + 1); u.insert(dist[i]); } for (auto &i: child[x]) dfs_rev_dist(i); } void dfs_edge(int x) { multiset<int> v; for (auto &i: child[x]) v.insert(max_depth[i] + 1); for (auto &i: child[x]) { v.erase(v.find(max_depth[i] + 1)); if ((int)v.size() > 1) edge[i] = *v.rbegin() + *prev(prev(v.end())); else if (!v.empty()) edge[i] = *v.rbegin(); v.insert(max_depth[i] + 1); } for (auto &i: child[x]) dfs_edge(i); } void dfs_child(int x, int prev = -1) { par[x] = prev; for (auto &i: tree[x]) if (i != prev) { child[x].push_back(i); dfs_child(i, x); } } int dfs_sz(int x) { sz[x] = 1; for (auto &i: child[x]) { depth[i] = depth[x] + 1; sz[x] += dfs_sz(i); if (sz[i] > sz[child[x][0]]) swap(child[x][0], i); } return sz[x]; } void dfs_hld(int x) { in[x] = T++; for (auto &i: child[x]) { top[i] = (i == child[x][0] ? top[x] : i); dfs_hld(i); } } int lca(int u, int v) { int ret = 0; while (top[u] != top[v]) { if (depth[top[u]] < depth[top[v]]) swap(u, v); ret += depth[u] - depth[par[top[u]]]; u = par[top[u]]; } if (depth[u] > depth[v]) swap(u, v); return u; } int pr(int x, int y) { for (int t = 17; t >= 0; t--) if (y >= 1 << t) { y -= 1 << t; x = sp[t][x]; } return x; } int tree_dist[524288], tree_edge[524288]; int query_dist(int i, int b, int e, int l, int r) { if (r < l || r < b || e < l) return 0; if (l <= b && e <= r) return tree_dist[i]; int m = (b + e) / 2; return max(query_dist(i * 2 + 1, b, m, l, r), query_dist(i * 2 + 2, m + 1, e, l, r)); } int query_edge(int i, int b, int e, int l, int r) { if (r < l || r < b || e < l) return 0; if (l <= b && e <= r) return tree_edge[i]; int m = (b + e) / 2; return max(query_edge(i * 2 + 1, b, m, l, r), query_edge(i * 2 + 2, m + 1, e, l, r)); } vector<pair<int, int>> lt; void query_hld(int u, int v) { while (top[u] != top[v]) { if (depth[top[u]] < depth[top[v]]) swap(u, v); lt.push_back({ in[top[u]], in[u] }); u = par[top[u]]; } lt.push_back({ min(in[u], in[v]), max(in[u], in[v]) }); } int query_hld_dist(int u, int v, int x, int y) { lt.clear(); query_hld(u, v); sort(lt.begin(), lt.end()); int ret = max(query_dist(0, 0, 262143, x, lt[0].first - 1), query_dist(0, 0, 262143, lt.back().second + 1, y)); for (int i = 1; i < (int)lt.size(); i++) ret = max(ret, query_dist(0, 0, 262143, lt[i - 1].second + 1, lt[i].first - 1)); return ret; } int query_hld_edge(int u, int v) { int ret = 0; while (top[u] != top[v]) { if (depth[top[u]] < depth[top[v]]) swap(u, v); ret = max(ret, query_edge(0, 0, 262143, in[top[u]], in[u])); u = par[top[u]]; } ret = max(ret, query_edge(0, 0, 262143, min(in[u], in[v]), max(in[u], in[v]))); return ret; } int main() { scanf("%d%d", &n, &m); while (m--) { int x, y, w; scanf("%d%d%d", &x, &y, &w); if (w == 1) { tree[x].push_back(y); tree[y].push_back(x); } else { adj[x].push_back({ y, w }); adj[y].push_back({ x, w }); } } dfs_child(0); dfs_sz(0); dfs_hld(0); dfs_dist(0); dfs_rev_dist(0); dfs_edge(0); for (int i = 0; i < n; i++) sp[0][i] = par[i]; for (int t = 1; t < 18; t++) for (int i = 0; i < n; i++) { if (sp[t - 1][i] == -1) sp[t][i] = -1; else sp[t][i] = sp[t - 1][sp[t - 1][i]]; } for (int i = 0; i < n; i++) { tree_dist[262143 + in[i]] = dist[i]; tree_edge[262143 + in[i]] = edge[i]; } for (int i = 262142; i >= 0; i--) { tree_dist[i] = max(tree_dist[i * 2 + 1], tree_dist[i * 2 + 2]); tree_edge[i] = max(tree_edge[i * 2 + 1], tree_edge[i * 2 + 2]); } for (int i = 0; i < n; i++) for (auto &j: child[i]) lt_depth[i].insert(max_depth[j]); int zero = 2 * (n - 1) - dist[0], one = (int)1e9; for (int i = 0; i < n; i++) { dfs(i); for (auto &j: adj[i]) if (i < j.first) { int l = lca(i, j.first); int ds = depth[i] + depth[j.first] - depth[l] - depth[l]; int curr = j.second + 2 * (n - 1) - ds - 1; int x = j.first, pv = -1; vector<pair<int, int>> v; int y = max(rev_dist[l] - 1, query_hld_dist(i, j.first, in[l], in[l] + sz[l] - 1) - 1), T = 0; int A = (i == l ? -1 : pr(i, depth[i] - depth[l] - 1)); int B = (j.first == l ? -1 : pr(j.first, depth[j.first] - depth[l] - 1)); int Ap = (depth[i] - depth[l] - 2 >= 0 ? pr(i, depth[i] - depth[l] - 2) : -1); int Bp = (depth[j.first] - depth[l] - 2 >= 0 ? pr(j.first, depth[j.first] - depth[l] - 2) : -1); { if (A != -1) lt_depth[l].erase(lt_depth[l].find(max_depth[A])); if (B != -1) lt_depth[l].erase(lt_depth[l].find(max_depth[B])); if (!lt_depth[l].empty()) y = max(y, *lt_depth[l].rbegin() + rev_max_depth[l]); else y = max(y, rev_max_depth[l]); if ((int)lt_depth[l].size() > 1) y = max(y, *lt_depth[l].rbegin() + *prev(prev(lt_depth[l].end())) - 1); if (A != -1) lt_depth[l].insert(max_depth[A]); if (B != -1) lt_depth[l].insert(max_depth[B]); } if (Ap != -1) y = max(y, query_hld_edge(Ap, i) - 1); if (Bp != -1) y = max(y, query_hld_edge(Bp, j.first) - 1); while (x != -1) { for (auto &k: tree[x]) if (k != pv && k != _par[x]) { if (_sz[k]) { if (!v.empty() && v.back().second == T) { //y = max(y, v.back().first + _sz[k] - 1); v.back().first = max(v.back().first, _sz[k]); } else v.push_back({ _sz[k], T }); } } T++; pv = x; x = _par[x]; } int ans = -(int)1e9; for (int i = 0; i < (int)v.size(); i++) { if (i) ans -= v[i].second - v[i - 1].second; y = max(y, ans + v[i].first + 1); ans = max(ans, v[i].first); } curr -= y; one = min(one, curr); } } printf("%d", min(zero, one)); }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:175:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:178:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |         scanf("%d%d%d", &x, &y, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...