Submission #940727

#TimeUsernameProblemLanguageResultExecution timeMemory
940727KK_1729Evacuation plan (IZhO18_plan)C++17
100 / 100
1020 ms141584 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define pb push_back #define all(a) a.begin(), a.end() #define endl "\n" void printVector(vector<int> a){ for (auto x: a) cout << x << " "; cout << endl; } int N = 0; vector<vector<pair<int, int>>> graph; vector<int> distance(vector<int> source){ // return ; using T = pair<long long, int>; priority_queue<T, vector<T>, greater<T>> pq; // stores dist, node vector<int> dist(N+1, 1e16); for (auto x: source){ pq.push({0, x}); dist[x] = 0; } while (!pq.empty()){ auto [cdist, node] = pq.top(); pq.pop(); if (cdist != dist[node]) continue; for (auto x: graph[node]){ if (cdist + x.second < dist[x.first]){ pq.push({dist[x.first] = cdist + x.second, x.first}); } } } return dist; } struct UFDS { vector<int> link, siz; UFDS(int n) : link(n), siz(n, 1) { iota(link.begin(), link.end(), 0); } //each element as its own subset, with size 1 int findRoot(int x) { return x == link[x] ? x : link[x] = findRoot(link[x]); } bool same(int x, int y) { return findRoot(x) == findRoot(y); } bool unite(int x, int y) { x = findRoot(x); y = findRoot(y); if (x == y) return false; if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; link[y] = x; return true; } int size(int x) { return siz[findRoot(x)]; } }; int min(int x, int y){ if (x < y) return x; else return y; } vector<vector<pair<int, int>>> maxtree; vector<int> up(N+1); int L = 0; vector<vector<int>> bin; vector<vector<int>> mbin; vector<int> depth; int lca(int a, int b){ if (depth[a] < depth[b]) swap(a, b); int k = depth[a]-depth[b]; for (int j = L-1; j >= 0; j--){ if (k & (1 << j)) a = bin[a][j]; } if (a == b) return a; for (int j = L-1; j >= 0; j--){ if (bin[a][j] != bin[b][j]){ a = bin[a][j]; b = bin[b][j]; } } return bin[a][0]; } void solve(){ int n, m; cin >> n >> m; N = n; graph.resize(n+1); FOR(i,0,m){ int a, b, w; cin >> a >> b >> w; graph[a].pb({b, w}); graph[b].pb({a, w}); } int k; cin >> k; vector<int> np(k); FOR(i,0,k) cin >> np[i]; vector<int> d = distance(np); vector<vector<int>> new_graph(n+1); vector<vector<int>> edges; FOR(i,1,n+1){ for (auto x: graph[i]){ edges.pb({min(d[x.first], d[i]), i, x.first}); } } UFDS ds(n+1); sort(all(edges)); reverse(all(edges)); maxtree.resize(n+1); for (auto edge: edges){ // printVector(edge); if (!ds.same(edge[1], edge[2])){ // cout << edge[1] << " " << edge[2] << " " << edge[0] << endl; ds.unite(edge[1], edge[2]); maxtree[edge[1]].pb({edge[2], edge[0]}); maxtree[edge[2]].pb({edge[1], edge[0]}); } } // FOR(i,1,n+1){ // for (auto x: maxtree[i]) cout << x.first << x.second << endl; // cout << endl; // } L = log2(n)+1; bin.resize(n+1, vector<int>(L+1)); mbin.resize(n+1, vector<int>(L+1)); depth.resize(n+1); stack<int> s; s.push(1); vector<int> vis(n+1); bin[1][0] = 1; depth[1] = 1; while (!s.empty()){ int current = s.top(); s.pop(); if (vis[current]) continue; for (auto x: maxtree[current]){ if (vis[x.first]) continue; bin[x.first][0] = current; mbin[x.first][0] = x.second; depth[x.first] = depth[current]+1; s.push(x.first); } vis[current] = 1; } for (int i = 1; i <= L; ++i){ for (int j = 1; j <= n; ++j){ bin[j][i] = bin[ bin[j][i-1] ][i-1]; mbin[j][i] = min(mbin[j][i-1], mbin[ bin[j][i-1] ][i-1]); } } int q; cin >> q; while (q--){ int a, b; cin >> a >> b; int l = lca(a, b); int k = depth[a]-depth[l]; int ans = 1e16; for (int i = L; i >= 0; i--){ if (k & (1 << i)){ ans = min(ans, mbin[a][i]); a = bin[a][i]; } } k = depth[b]-depth[l]; for (int i = L; i >= 0; i--){ if (k & (1 << i)){ ans = min(ans, mbin[b][i]); b = bin[b][i]; } } cout << ans << endl; } } int32_t main(){ ios::sync_with_stdio(false);cin.tie(0); int t = 1; // cin >> t; while (t--) solve(); }
#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...