Submission #715263

#TimeUsernameProblemLanguageResultExecution timeMemory
715263StickfishEvacuation plan (IZhO18_plan)C++17
100 / 100
1342 ms47212 KiB
#include <iostream> #include <vector> #include <algorithm> #include <set> using namespace std; struct dsu { void resize(int n) { rt.resize(n); sz.assign(n, 1); for (int i = 0; i < n; ++i) rt[i] = {i, 0}; } int gst(int i) { if (rt[i].first == i) return i; return gst(rt[i].first); } int gstwr(int i, int mxw) { if (rt[i].first == i || rt[i].second > mxw) return i; return gstwr(rt[i].first, mxw); } void unite(int i, int j, int w) { i = gst(i); j = gst(j); if (i == j) return; if (sz[i] < sz[j]) swap(i, j); sz[i] += sz[j]; rt[j] = {i, w}; } private: vector<pair<int, int>> rt; vector<int> sz; }; const int MAXN = 1e5 + 123; const int INF = 1e9 + 177013; vector<pair<int, int>> edgw[MAXN]; vector<int> edg[MAXN]; int depth[MAXN]; void get_depth(int n) { int k; cin >> k; vector<int> sts(k); for (int i = 0; i < k; ++i) cin >> sts[i], --sts[i]; set<pair<int, int>> rdepth; for (int i = 0; i < n; ++i) depth[i] = INF; for (auto i : sts) { depth[i] = 0; rdepth.insert({depth[i], i}); } while (rdepth.size()) { auto [d, v] = *rdepth.begin(); rdepth.erase(rdepth.begin()); if (depth[v] < d) continue; for (auto [u, w] : edgw[v]) { if (depth[u] > d + w) { depth[u] = d + w; rdepth.insert({depth[u], u}); } } } } signed main() { int n, m; cin >> n >> m; for (int t = 0; t < m; ++t) { int u, v, w; cin >> u >> v >> w; --u, --v; edgw[u].push_back({v, w}); edgw[v].push_back({u, w}); edg[u].push_back(v); edg[v].push_back(u); } get_depth(n); //for (int i = 0; i < n; ++i) //cout << depth[i] << ' '; //cout << endl; vector<pair<int, pair<int, int>>> edges; for (int v = 0; v < n; ++v) for (auto u : edg[v]) { if (u > v) edges.push_back({min(depth[v], depth[u]), {v, u}}); } sort(edges.rbegin(), edges.rend()); dsu su; su.resize(n); for (int i = 0; i < m; ++i) { su.unite(edges[i].second.first, edges[i].second.second, i); } int q; cin >> q; while (q--) { int s, t; cin >> s >> t; --s, --t; int lb = -1, ub = m; while (ub - lb > 1) { int mb = (lb + ub) / 2; if (su.gstwr(s, mb) == su.gstwr(t, mb)) ub = mb; else lb = mb; } cout << min({edges[ub].first, depth[s], depth[t]}) << '\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...