제출 #570110

#제출 시각아이디문제언어결과실행 시간메모리
570110SSRSEvacuation plan (IZhO18_plan)C++14
22 / 100
4064 ms16208 KiB
#define _GLIBCXX_DEBUG #include <bits/stdc++.h> using namespace std; 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[x] += p[y]; p[y] = x; } } }; int main(){ 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)); } } } } 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 (int i = 0; i < n; i++){ for (auto P : E[i]){ int j = P.second; query.push_back(make_tuple(min(d[i], d[j]), 1, i, j)); } } sort(query.begin(), query.end(), greater<tuple<int, int, int, int>>()); int cnt = query.size(); unionfind UF(n); for (int i = 0; i < cnt; i++){ int x = get<1>(query[i]); if (x == 0){ int id = get<2>(query[i]); if (UF.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]); UF.unite(u, v); } } } for (int i = 0; i < Q; i++){ cout << tv[i] << endl; } }
#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...