| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 878780 | The_Samurai | Evacuation plan (IZhO18_plan) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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'; }}