제출 #1112642

#제출 시각아이디문제언어결과실행 시간메모리
1112642MisterReaperEvacuation plan (IZhO18_plan)C++17
100 / 100
689 ms33716 KiB
#include <bits/stdc++.h> using i64 = long long; #ifdef DEBUG #include "../../../debug.h" #else #define debug(...) void(23) #endif constexpr int INF = int(1E9); constexpr int max_N = int(1E5) + 5; bool chmin(int& a, int b) { if (a > b) { a = b; return true; } return false; } int N, M; std::vector<std::pair<int, int>> adj[max_N]; std::vector<int> dist; struct DSU { std::vector<int> f, siz; DSU() {} DSU(int n) { init(n); } void init(int n) { f.assign(n, 0); siz.assign(n, 1); std::iota(f.begin(), f.end(), 0); } int get(int x) { while (f[x] != x) { x = f[x] = f[f[x]]; } return x; } bool unite(int a, int b) { a = get(a), b = get(b); if (a == b) { return false; } else if (siz[a] > siz[b]) { std::swap(a, b); } f[a] = b; siz[b] += siz[a]; return true; } bool same(int a, int b) { return get(a) == get(b); } int size(int x) { return siz[get(x)]; } }; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cin >> N >> M; for (int i = 0; i < M; ++i) { int A, B, C; std::cin >> A >> B >> C; --A, --B; adj[A].emplace_back(B, C); adj[B].emplace_back(A, C); } dist.assign(N, INF); std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq; int K; std::cin >> K; for (int i = 0, x; i < K; ++i) { std::cin >> x; --x; pq.emplace(dist[x] = 0, x); } while (!pq.empty()) { auto[d, v] = pq.top(); pq.pop(); if (dist[v] != d) { continue; } for (auto[u, w] : adj[v]) { if (chmin(dist[u], d + w)) { pq.emplace(dist[u], u); } } } debug(dist); int Q; std::cin >> Q; std::vector<int> ans(Q); std::vector<std::pair<int, int>> qq(Q); for (int i = 0; i < Q; ++i) { std::cin >> qq[i].first >> qq[i].second; --qq[i].first, --qq[i].second; } std::vector<std::tuple<int, int, int>> pv(Q); for (int i = 0; i < Q; ++i) { pv[i] = {0, INF, i}; } std::vector<int> ord(N); std::iota(ord.begin(), ord.end(), 0); std::sort(ord.begin(), ord.end(), [&](auto lhs, auto rhs) { return dist[lhs] > dist[rhs]; }); DSU dsu; std::vector<int> act; for (int i = 0; i < 31; ++i) { std::sort(pv.rbegin(), pv.rend()); int cur = 0; dsu.init(N); act.assign(N, false); auto work = [&](int x) -> void { while (cur < N && dist[ord[cur]] >= x) { int v = ord[cur]; act[v] = true; for (auto[u, w] : adj[v]) { if (act[u]) { dsu.unite(u, v); } } ++cur; } }; std::vector<std::tuple<int, int, int>> new_pv; for (auto[lo, hi, idx] : pv) { if (lo == hi) { ans[idx] = lo; continue; } int mid = (lo + hi) >> 1; work(mid); if (!dsu.same(qq[idx].first, qq[idx].second)) { new_pv.emplace_back(lo, mid, idx); } else { new_pv.emplace_back(mid + 1, hi, idx); } } pv.swap(new_pv); } for (int i = 0; i < Q; ++i) { std::cout << ans[i] - 1 << '\n'; } return 0; }
#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...