Submission #1082927

#TimeUsernameProblemLanguageResultExecution timeMemory
1082927avighnaAesthetic (NOI20_aesthetic)C++17
51 / 100
2060 ms65052 KiB
#include <bits/stdc++.h> typedef long long ll; struct To { ll v, w; ll i; }; const ll inf = 1e15; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); ll n, m; std::cin >> n >> m; std::vector<std::vector<To>> adj(n + 1); std::vector<ll> roads(m); std::vector<std::pair<ll, ll>> edges; for (ll i = 0, u, v, w; i < m; ++i) { std::cin >> u >> v >> w; adj[u].push_back({v, w, i}); adj[v].push_back({u, w, i}); roads[i] = w; edges.push_back({u, v}); } if (m == n - 1) { // there will only be one path std::set<ll> edges; std::function<bool(ll, ll)> dfs; ll def = 0; dfs = [&](ll node, ll par) { if (node == n) { return true; } for (auto &[ch, w, i] : adj[node]) { if (ch == par) { continue; } if (dfs(ch, node)) { edges.insert(i); def += w; return true; } } return false; }; dfs(1, 0); ll ans = def; ll worst_road = roads[m - 1]; for (ll i = m - 2; i >= 0; --i) { if (edges.count(i)) { ans = std::max(ans, def + worst_road); } worst_road = std::max(worst_road, roads[i]); } std::cout << ans << '\n'; return 0; } if (m == n) { // find the cycle std::vector<std::pair<ll, ll>> up(n + 1); std::function<void(ll, ll)> dfs; std::vector<bool> vis(n + 1); bool found = false; ll begin_node = -1; dfs = [&](ll node, ll par) { if (found) { return; } if (vis[node]) { return; } vis[node] = true; for (auto &[ch, w, i] : adj[node]) { if (ch == par) { continue; } up[ch] = {node, i}; if (vis[ch]) { begin_node = node; found = true; return; } dfs(ch, node); if (found) { return; } }; }; dfs(1, 0); std::set<ll> cycle_edegs; ll tot_cyc_wt = 0; if (found) { vis.assign(n + 1, false); while (!vis[begin_node]) { vis[begin_node] = true; cycle_edegs.insert(up[begin_node].second); tot_cyc_wt += roads[up[begin_node].second]; begin_node = up[begin_node].first; } } std::set<ll> shortest_path_edges; ll shortest_cyc_wt = 0; ll def = 0; auto sssp = [&]() { std::vector<ll> ans(n + 1, inf); std::vector<bool> vis(n + 1); std::vector<std::pair<ll, ll>> up(n + 1); std::priority_queue<std::pair<ll, ll>> pq; pq.push({0, 1}); while (!pq.empty()) { auto [d, node] = pq.top(); d *= -1; pq.pop(); if (vis[node]) { continue; } vis[node] = true; for (auto [ch, w, cur_i] : adj[node]) { if (ans[ch] > d + w) { up[ch] = {node, cur_i}; ans[ch] = d + w; pq.push({-ans[ch], ch}); } } } def = ans[n]; ll end = n; while (end != 1) { shortest_path_edges.insert(up[end].second); if (cycle_edegs.count(up[end].second)) { shortest_cyc_wt += roads[up[end].second]; } end = up[end].first; } }; sssp(); ll ans = def; ll worst_road = roads[m - 1]; for (ll i = m - 2; i >= 0; --i) { if (shortest_path_edges.count(i)) { if (cycle_edegs.count(i)) { ans = std::max(ans, std::min(def + worst_road, def - 2 * shortest_cyc_wt + tot_cyc_wt)); } else { ans = std::max(ans, def + worst_road); } } worst_road = std::max(worst_road, roads[i]); } std::cout << ans << '\n'; return 0; }; if (*std::max_element(roads.begin(), roads.end()) == 1 and *std::min_element(roads.begin(), roads.end()) == 1) { // w_i = 1 auto sssp = [&](ll node) { std::vector<ll> ans(n + 1, inf); std::vector<bool> vis(n + 1); std::priority_queue<std::pair<ll, ll>> pq; ans[node] = 0; pq.push({0, node}); while (!pq.empty()) { auto [d, node] = pq.top(); d *= -1; pq.pop(); if (vis[node]) { continue; } vis[node] = true; for (auto [ch, w, cur_i] : adj[node]) { if (ans[ch] > d + w) { ans[ch] = d + w; pq.push({-ans[ch], ch}); } } } return ans; }; auto sssp1 = sssp(1); auto ssspn = sssp(n); std::set<ll> special_edges; std::map<std::pair<ll, ll>, ll> edge_starts; for (ll i = 0; i < edges.size(); ++i) { auto [u, v] = edges[i]; if (std::min(sssp1[u] + 1 + ssspn[v], sssp1[v] + 1 + ssspn[u]) == sssp1[n]) { special_edges.insert(i); if (sssp1[u] + 1 + ssspn[v] == sssp1[n]) { edge_starts[{sssp1[u], ssspn[v]}]++; } else { edge_starts[{sssp1[v], ssspn[u]}]++; } } } ll ans = sssp1[n]; for (ll i = 0; i <= m - 2; ++i) { auto [u, v] = edges[i]; if (special_edges.count(i) and ((edge_starts[{sssp1[u], ssspn[v]}] == 1 and sssp1[u] + 1 + ssspn[v] == sssp1[n]) or (edge_starts[{sssp1[v], sssp1[u]}] == 1 and sssp1[v] + 1 + ssspn[u]))) { ans = std::max(ans, sssp1[n] + 1); } } std::cout << ans << '\n'; return 0; } // exclude edge i auto sssp = [&](ll i, ll add) { std::vector<ll> ans(n + 1, inf); std::vector<bool> vis(n + 1); std::priority_queue<std::pair<ll, ll>> pq; pq.push({0, 1}); while (!pq.empty()) { auto [d, node] = pq.top(); d *= -1; pq.pop(); if (vis[node]) { continue; } vis[node] = true; for (auto [ch, w, cur_i] : adj[node]) { if (cur_i == i) { w += add; } if (ans[ch] > d + w) { ans[ch] = d + w; pq.push({-ans[ch], ch}); } } } return ans; }; ll def = sssp(-1, 0)[n]; ll ans = def; ll worst_road = roads[m - 1]; for (ll i = m - 2; i >= 0; --i) { ans = std::max(ans, sssp(i, worst_road)[n]); worst_road = std::max(worst_road, roads[i]); } std::cout << ans << '\n'; }

Compilation message (stderr)

Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:195:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |     for (ll i = 0; i < edges.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...