| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 878780 | The_Samurai | Evacuation plan (IZhO18_plan) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <random> #include "bits/stdc++.h"using namespace std;using ll = long long;const int inf = 1e9;const int N = 1e5 + 5; vector<pair<int, int>> g[N], queries[N];pair<int, int> danger[N];vector<bool> vis(N);vector<int> v[N];int ans[N], now, p[N], sz[N]; int get(int a) { return p[a] == a ? a : p[a] = get(p[a]);} void add(int a, int b) { a = get(a); b = get(b); if (a == b) return; if (sz[a] > sz[b]) swap(a, b); sz[b] += sz[a]; for (int s: v[a]) { for (auto [t, i]: queries[s]) { if (get(t) == b) ans[i] = now; } v[b].emplace_back(s); } p[a] = b;} void solve() { int n, m, q; cin >> n >> m; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } for (int i = 1; i <= n; i++) danger[i] = make_pair(inf, i); { int k; cin >> k; priority_queue<pair<int, int>> pq; for (int i = 0; i < k; i++) { int root; cin >> root; pq.emplace(0, root); danger[root].first = 0; } while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); d = -d; if (vis[u]) continue; vis[u] = true; for (auto [v, w]: g[u]) { if (danger[v].first <= d + w) continue; danger[v].first = d + w; pq.emplace(-danger[v].first, v); } } sort(danger + 1, danger + n + 1); } cin >> q; vector<int> copy(n + 1); for (int i = 0; i < q; i++) { int s, t; cin >> s >> t; queries[s].emplace_back(t, i); queries[t].emplace_back(s, i); } for (int i = 1; i <= n; i++) { copy[danger[i].second] = danger[i].first; p[i] = i; sz[i] = (int) queries[i].size() + 1; v[i] = {i}; } for (int i = n; i > 0; i--) { now = danger[i].first; int u = danger[i].second; for (auto [vv, w]: g[u]) { if (copy[vv] < now) continue; add(u, vv); } } for (int i = 0; i < q; i++) cout << ans[i] << '\n';} int main() { srand(time(0)); cin.tie(0)->sync_with_stdio(false);#ifdef sunnatov freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);#endif int queries = 1;// cin >> queries; for (int test_case = 1; test_case <= queries; test_case++) {#ifdef sunnatov cout << "Test case: " << test_case << endl;#endif solve(); cout << '\n'; }}