제출 #570128

#제출 시각아이디문제언어결과실행 시간메모리
570128SSRSEvacuation plan (IZhO18_plan)C++14
100 / 100
1157 ms47512 KiB
#include <bits/stdc++.h> using namespace std; const int LOG = 17; const int INF = 1000000000; struct unionfind{ vector<int> p; unionfind(int N): p(N, -1){ } int root(int x){ if (p[x] < 0){ return x; } else { p[x] = root(p[x]); return p[x]; } } bool same(int x, int y){ return root(x) == root(y); } void unite(int x, int y){ x = root(x); y = root(y); if (x != y){ if (p[x] < p[y]){ swap(x, y); } p[y] += p[x]; p[x] = y; } } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<pair<int, int>>> E(n); for (int i = 0; i < m; i++){ int a, b, w; cin >> a >> b >> w; a--; b--; E[a].push_back(make_pair(w, b)); E[b].push_back(make_pair(w, a)); } int k; cin >> k; vector<int> g(k); for (int i = 0; i < k; i++){ cin >> g[i]; g[i]--; } vector<int> d(n, -1); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for (int i = 0; i < k; i++){ pq.push(make_pair(0, g[i])); } while (!pq.empty()){ int c = pq.top().first; int v = pq.top().second; pq.pop(); if (d[v] == -1){ d[v] = c; for (auto P : E[v]){ int w = P.second; if (d[w] == -1){ pq.push(make_pair(c + P.first, w)); } } } } vector<tuple<int, int, int>> E2; for (int i = 0; i < n; i++){ for (auto P : E[i]){ int j = P.second; if (i < j){ E2.push_back(make_tuple(min(d[i], d[j]), i, j)); } } } sort(E2.begin(), E2.end(), greater<tuple<int, int, int>>()); unionfind UF(n); vector<tuple<int, int, int>> E3; for (int i = 0; i < m; i++){ int u = get<1>(E2[i]); int v = get<2>(E2[i]); if (!UF.same(u, v)){ UF.unite(u, v); int c = get<0>(E2[i]); E3.push_back(make_tuple(c, u, v)); } } int Q; cin >> Q; vector<int> s(Q), t(Q); for (int i = 0; i < Q; i++){ cin >> s[i] >> t[i]; s[i]--; t[i]--; } vector<int> tv(Q, 0); vector<int> fv(Q, INF); while (true){ bool ok = true; vector<tuple<int, int, int, int>> query; for (int i = 0; i < Q; i++){ if (fv[i] - tv[i] > 1){ ok = false; query.push_back(make_tuple((tv[i] + fv[i]) / 2, 0, i, -1)); } } if (ok){ break; } for (auto e : E3){ query.push_back(make_tuple(get<0>(e), 1, get<1>(e), get<2>(e))); } sort(query.begin(), query.end(), greater<tuple<int, int, int, int>>()); int cnt = query.size(); unionfind UF2(n); for (int i = 0; i < cnt; i++){ int x = get<1>(query[i]); if (x == 0){ int id = get<2>(query[i]); if (UF2.same(s[id], t[id])){ tv[id] = (tv[id] + fv[id]) / 2; } else { fv[id] = (tv[id] + fv[id]) / 2; } } if (x == 1){ int u = get<2>(query[i]); int v = get<3>(query[i]); UF2.unite(u, v); } } } for (int i = 0; i < Q; i++){ cout << tv[i] << "\n"; } }
#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...