제출 #556337

#제출 시각아이디문제언어결과실행 시간메모리
556337ngpin04Evacuation plan (IZhO18_plan)C++14
100 / 100
1010 ms32748 KiB
#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define TASK "" #define ALL(x) (x).begin(), (x).end() using namespace std; template <typename T1, typename T2> bool mini(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maxi(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } const int N = 1e5 + 5; const int oo = 1e9; const long long ooo = 1e18; const int mod = 1e9 + 7; // 998244353; const long double pi = acos(-1); vector <pair <int, int>> adj[N]; vector <int> qr[N]; int par[N]; int lo[N]; int hi[N]; int s[N]; int t[N]; int d[N]; int n,m,k,q; int getpar(int u) { return (par[u] < 0) ? u : (par[u] = getpar(par[u])); } void join(int u, int v) { u = getpar(u); v = getpar(v); if (u == v) return; if (par[u] > par[v]) swap(u, v); par[u] += par[v]; par[v] = u; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); #ifdef ONLINE_JUDGE // freopen(TASK".inp","r",stdin); // freopen(TASK".out","w",stdout); #endif cin >> n >> m; for (int i = 1; i <= m; i++) { int u,v,w; cin >> u >> v >> w; adj[u].push_back(mp(v, w)); adj[v].push_back(mp(u, w)); } cin >> k; for (int i = 1; i <= n; i++) d[i] = oo; priority_queue <pair <int, int>> heap; for (int i = 1; i <= k; i++) { int v; cin >> v; d[v] = 0; heap.push(mp(0, v)); } while (heap.size()) { int u = heap.top().se; int cur = -heap.top().fi; heap.pop(); if (cur != d[u]) continue; for (pair <int, int> to : adj[u]) { int v = to.fi; int w = to.se; if (mini(d[v], d[u] + w)) heap.push(mp(-d[v], v)); } } vector <int> node(n, 0); iota(ALL(node), 1); sort(ALL(node), [](int i, int j) { return d[i] < d[j]; }); cin >> q; for (int i = 1; i <= q; i++) { cin >> s[i] >> t[i]; lo[i] = 0; hi[i] = n; } for (int rep = 0; rep < 20; rep++) { for (int i = 0; i < n; i++) qr[i].clear(); for (int i = 1; i <= q; i++) { int mid = (lo[i] + hi[i]) >> 1; qr[mid].push_back(i); } memset(par, 0, sizeof(par)); for (int i = n - 1; i >= 0; i--) { int u = node[i]; par[u] = -1; for (pair <int, int> to : adj[u]) { int v = to.fi; if (par[v] != 0) join(u, v); } for (int j : qr[i]) { int u = s[j]; int v = t[j]; if (par[u] != 0 && par[v] != 0 && getpar(u) == getpar(v)) lo[j] = i; else hi[j] = i; } } } for (int i = 1; i <= q; i++) cout << d[node[lo[i]]] << "\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...