제출 #743561

#제출 시각아이디문제언어결과실행 시간메모리
743561LeonaRagingEvacuation plan (IZhO18_plan)C++14
100 / 100
1657 ms42984 KiB
#include <bits/stdc++.h> using namespace std; #define T pair<int,int> #define pb emplace_back #define db(val) "[" #val " = " << (val) << "] " const int maxn = 1e5 + 4; struct DisjointSet { vector<int> par, Rank; DisjointSet(int n) { par.resize(n + 4); Rank.resize(n + 4); for (int i = 1; i <= n; i++) par[i] = i, Rank[i] = 1; } int find(int x) { if (x != par[x]) par[x] = find(par[x]); return par[x]; } bool join(int u, int v) { u = find(u); v = find(v); if (u == v) return 0; if (Rank[u] < Rank[v]) swap(u, v); Rank[u] += Rank[v]; par[v] = u; return 1; } }; int n, m, dis[maxn], s[maxn], t[maxn], L[maxn], R[maxn], res[maxn]; vector<T> adj[maxn]; T node[maxn]; vector<int> vals, myVec[maxn]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1, u, v, w; i <= m; i++) { cin >> u >> v >> w; adj[u].pb(v, w); adj[v].pb(u, w); } priority_queue<T, vector<T>, greater<T>> pq; int q; cin >> q; memset(dis, 63, sizeof dis); while (q--) { int u; cin >> u; pq.push({0, u}); dis[u] = 0; } while (!pq.empty()) { int d, u; tie(d, u) = pq.top(); pq.pop(); node[u] = {dis[u], u}; if (dis[u] != d) continue; for (auto it : adj[u]) { int v, w; tie(v, w) = it; if (dis[u] + w < dis[v]) dis[v] = dis[u] + w, pq.push({dis[v], v}); } } sort(node + 1, node + 1 + n); sort(vals.begin(), vals.end()); cin >> q; for (int i = 1; i <= q; i++) cin >> s[i] >> t[i], L[i] = 1, R[i] = n; for (int time = 1; time <= 30; time++) { for (int i = 1; i <= q; i++) myVec[(L[i] + R[i]) / 2].pb(i); DisjointSet Dsu(n); for (int i = n; i >= 1; i--) { int u = node[i].second; for (auto it : adj[u]) { int v, w; tie(v, w) = it; if (dis[v] >= dis[u]) Dsu.join(u, v); } while (!myVec[i].empty()) { int id = myVec[i].back(); myVec[i].pop_back(); if (Dsu.find(s[id]) == Dsu.find(t[id])) res[id] = dis[u], L[id] = i + 1; else R[id] = i - 1; } } } for (int i = 1; i <= q; i++) cout << res[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...