Submission #517616

#TimeUsernameProblemLanguageResultExecution timeMemory
517616pavementRelay Marathon (NOI20_relaymarathon)C++17
5 / 100
246 ms19260 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #endif #define int long long #define mp make_pair #define mt make_tuple #define pb push_back #define ppb pop_back #define eb emplace_back #define g0(a) get<0>(a) #define g1(a) get<1>(a) #define g2(a) get<2>(a) #define g3(a) get<3>(a) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef double db; typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef tuple<int, int, int> iii; typedef tuple<int, int, int, int> iiii; typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; int N, M, K, ans = LLONG_MAX, ddist[100005]; bool yes[100005]; ii dist[100005]; iii ed[100005]; vector<ii> adj[100005]; priority_queue<ii, vector<ii>, greater<ii> > pq; pair<int, ii> shortest_pair() { int fp = LLONG_MAX; ii fpp; for (int i = 1; i <= N; i++) { if (yes[i]) { dist[i] = mp(0, i); pq.emplace(0, i); } else dist[i] = mp(LLONG_MAX, -1ll); } while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d != dist[u].first) continue; for (auto v : adj[u]) if (dist[v.first] > mp(d + v.second, dist[u].second)) { dist[v.first] = mp(d + v.second, dist[u].second); pq.emplace(dist[v.first].first, v.first); } } for (int i = 1, u, v, w; i <= M; i++) { tie(u, v, w) = ed[i]; if (dist[u].second != -1 && dist[u].second != dist[v].second && dist[u].first + dist[v].first + w < fp) { fp = dist[u].first + dist[v].first + w; fpp = mp(dist[u].second, dist[v].second); } } return mp(fp, fpp); } void dijk(int s) { for (int i = 1; i <= N; i++) if (i == s) ddist[i] = 0; else ddist[i] = LLONG_MAX; pq.emplace(0, s); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d != ddist[u]) continue; for (auto v : adj[u]) if (ddist[v.first] > d + v.second) { ddist[v.first] = d + v.second; pq.emplace(ddist[v.first], v.first); } } } main() { ios::sync_with_stdio(0); cin.tie(0); cin >> N >> M >> K; for (int i = 1, u, v, w; i <= M; i++) { cin >> u >> v >> w; adj[u].eb(v, w); adj[v].eb(u, w); ed[i] = mt(u, v, w); } for (int i = 1, x; i <= K; i++) { cin >> x; yes[x] = 1; } auto f = shortest_pair(); yes[f.second.first] = yes[f.second.second] = 0; auto s = shortest_pair(); ans = min(ans, f.first + s.first); yes[f.second.first] = yes[f.second.second] = 1; dijk(f.second.first); for (int i = 1; i <= N; i++) if (yes[i] && i != f.second.first && i != f.second.second) s = min(s, mp(ddist[i], mp(f.second.first, i))); dijk(f.second.second); for (int i = 1; i <= N; i++) if (yes[i] && i != f.second.first && i != f.second.second) s = min(s, mp(ddist[i], mp(f.second.second, i))); if (f.second.first != s.second.first && f.second.first != s.second.second && f.second.second != s.second.first && f.second.second != s.second.second) ans = min(ans, f.first + s.first); else { int fff, sss, common; yes[s.second.first] = yes[s.second.second] = 0; auto ff = shortest_pair(); ans = min(ans, ff.first + s.first); yes[s.second.first] = yes[s.second.second] = 1; for (int x : {f.second.first, f.second.second}) if (x == s.second.first || x == s.second.second) common = x; for (int x : {f.second.first, f.second.second}) if (x != common) fff = x; for (int x : {s.second.first, s.second.second}) if (x != common) sss = x; yes[fff] = yes[sss] = 0; auto ffff = shortest_pair(); dijk(fff); ans = min(ans, ffff.first + ddist[sss]); yes[fff] = yes[sss] = 1; } cout << ans << '\n'; }

Compilation message (stderr)

RelayMarathon.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   81 | main() {
      | ^~~~
RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:123:12: warning: 'fff' may be used uninitialized in this function [-Wmaybe-uninitialized]
  123 |   yes[fff] = yes[sss] = 1;
      |   ~~~~~~~~~^~~~~~~~~~~~~~
RelayMarathon.cpp:122:40: warning: 'sss' may be used uninitialized in this function [-Wmaybe-uninitialized]
  122 |   ans = min(ans, ffff.first + ddist[sss]);
      |                               ~~~~~~~~~^
RelayMarathon.cpp:116:4: warning: 'common' may be used uninitialized in this function [-Wmaybe-uninitialized]
  116 |    if (x != common) fff = x;
      |    ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...