Submission #577214

#TimeUsernameProblemLanguageResultExecution timeMemory
577214eecsMountains and Valleys (CCO20_day1problem3)C++17
16 / 25
1475 ms99236 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 5010; int n, m, par[maxn][maxn], len[maxn], suf[maxn], mx[maxn]; bool mark[maxn]; vector<int> G[maxn]; int main() { ios::sync_with_stdio(0), cin.tie(0); cin >> n >> m; vector<array<int, 3>> E; while (m--) { int u, v, w; cin >> u >> v >> w; if (w == 1) G[u].push_back(v), G[v].push_back(u); else if (w < (n + 1) / 2) E.push_back({u, v, w}); } int diam = 0; for (int i = 0; i < n; i++) { auto dfs = [&](auto self, int u, int fa, int d) -> void { diam = max(diam, d), par[i][u] = fa; for (int v : G[u]) if (v ^ fa) self(self, v, u, d + 1); }; dfs(dfs, i, -1, 0); } int ans = 2 * (n - 1) - diam; for (auto &e : E) { int u = e[0], v = e[1], mn = INT_MAX; memset(mark, 0, sizeof(mark)); vector<int> path; for (int i = u; ; i = par[v][i]) { path.push_back(i), mark[i] = 1; if (i == v) break; } for (int i = 0; i < path.size(); i++) { auto dfs = [&](auto self, int u, int fa) -> void { mx[u] = 0; int sec = 0; for (int v : G[u]) if (!mark[v] && v ^ fa) { self(self, v, u); if (mx[v] + 1 > mx[u]) sec = mx[u], mx[u] = mx[v] + 1; else if (mx[v] + 1 > sec) sec = mx[v] + 1; } mn = min(mn, 2 * (n - 2) - (int)path.size() + 3 - mx[u] - sec); }; dfs(dfs, path[i], -1), len[i] = mx[path[i]]; } for (int i = path.size() - 1; ~i; i--) { suf[i] = max((int)path.size() - i - 1 + len[i], i + 1 == path.size() ? 0 : suf[i + 1]); } for (int i = 0, mx = 0; i + 1 < path.size(); i++) { mx = max(mx, i + len[i]); mn = min(mn, 2 * (n - 2) - mx - suf[i + 1]); } ans = min(ans, mn + e[2]); } cout << ans << "\n"; return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int i = 0; i < path.size(); i++) {
      |                         ~~^~~~~~~~~~~~~
Main.cpp:50:67: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             suf[i] = max((int)path.size() - i - 1 + len[i], i + 1 == path.size() ? 0 : suf[i + 1]);
      |                                                             ~~~~~~^~~~~~~~~~~~~~
Main.cpp:52:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for (int i = 0, mx = 0; i + 1 < path.size(); i++) {
      |                                 ~~~~~~^~~~~~~~~~~~~
#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...