제출 #525833

#제출 시각아이디문제언어결과실행 시간메모리
525833mjhmjh1104Mountains and Valleys (CCO20_day1problem3)C++17
16 / 25
7056 ms41612 KiB
#include <set> #include <cstdio> #include <vector> #include <utility> #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 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 max_depth[200006], rev_max_depth[200006], dist[200006], rev_dist[200006]; 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_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 tree_dist[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)); } 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 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); for (int i = 0; i < n; i++) tree_dist[262143 + in[i]] = dist[i]; for (int i = 262142; i >= 0; i--) tree_dist[i] = max(tree_dist[i * 2 + 1], tree_dist[i * 2 + 2]); 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; 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)); }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:134:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:137:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         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...