Submission #316768

#TimeUsernameProblemLanguageResultExecution timeMemory
316768ajpianoEvacuation plan (IZhO18_plan)C++14
0 / 100
1228 ms73556 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") using namespace std; #define FOR(a,b) for(int a=0;a<b;a++) #define F0R(a,b,c) for(int a = b; a<=c; a++) #define f first #define s second #define m0(x) memset(x,0,sizeof(x)) #define all(x) x.begin(), x.end() typedef pair<int,int> pi; typedef long long ll; typedef vector<int> vi; typedef vector<pi> vpi; const int large = 1e5; struct path{ int start, finish, val, cost; path(int s, int f, int c){ start = s; finish = f; cost = c; } bool operator > (const path &b) const{ return (val >= b.val); } int other(int x){ if(x == start) return finish; else return start; } }; int n,m; int cur; vi edges[large+1]; vector<path> roads; vi parents; vi dist; vi members[large+1]; vpi transfers[large+1]; int bpath(int a, int b){ int asz = transfers[a].size(); int bsz = transfers[b].size(); if(asz > bsz){ swap(a,b); swap(asz,bsz); } int ans = 0; F0R(i,1,asz){ pi aval = transfers[a][asz-i]; pi bval = transfers[b][bsz-i]; if(aval.f != bval.f) break; ans = min(aval.s, bval.s); // cerr << "Group: " << aval.f << ", Meeting: " << aval.s << " " << bval.s << " - " << ans << "\n"; } return ans; } void mergeNode(int a, int b){ a = parents[a]; b = parents[b]; if(a == b) return; if(members[a].size() < members[b].size()) swap(a,b); // cerr << "Merge: " << b << " -> " << a << " : " << cur << "\n"; for(auto &node : members[b]){ members[a].push_back(node); parents[node] = a; transfers[node].push_back({a,cur}); } } const int inf = 1e9; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; parents.resize(n+1); iota(all(parents),0); dist.resize(n+1,inf); F0R(i,1,n) members[i].push_back(i); F0R(i,1,n) transfers[i].push_back({i,inf}); FOR(i,m){ int a, b, w; cin >> a >> b >> w; roads.emplace_back(a,b,w); edges[a].push_back(i); edges[b].push_back(i); } //run dijkstra priority_queue<pi, vpi, greater<pi>> pq; int k; cin >> k; FOR(i,k){ int a; cin >> a; dist[a] = 0; pq.push({0,a}); } while(!pq.empty()){ pi a = pq.top(); pq.pop(); if(dist[a.s] < a.f) continue; for(int e: edges[a.s]){ path &p = roads[e]; int b = p.other(a.s); if(a.f+p.cost >= dist[b]) continue; dist[b] = a.f+p.cost; pq.push({dist[b], b}); } } //assign values to paths FOR(i,m){ path &a = roads[i]; a.val = min(dist[a.start], dist[a.finish]); } // cerr << "Distances:\n"; // F0R(i,1,n){ // cerr << "Node: " << i << " : " << dist[i] << "\n"; // } // cerr << "END Distances\n"; // cerr << "Distances:\n"; // FOR(i,m){ // cerr << roads[i].start << " <--> " << roads[i].finish << " : " << roads[i].val << "\n"; // } // cerr << "END Distances\n"; //sort roads sort(all(roads), greater<path>()); //go through roads and do dsu for(path &p : roads){ cur = p.val; mergeNode(p.start, p.finish); } //answer queries int q; cin >> q; FOR(i,q){ int a, b; cin >> a >> b; // cout << "Answer " << i << ": " << bpath(a,b) << "\n"; cout << bpath(a,b) << "\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...