Submission #1326841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326841		husseinjuanda	Evacuation plan (IZhO18_plan)	C++20	100 / 100	400 ms	45268 KiB

plan

#include <bits/stdc++.h>
#define int long long
using namespace std; vector<int> ans; vector<int> par; vector<vector<int>> isi; vector<vector<pair<int, int>>> que; int fpar(int k){ if(par[k] == k) return k; par[k] = fpar(par[k]); return par[k]; } int cursz = 0; void merge(int k, int f){ k = fpar(k); f = fpar(f); if(k == f) return; if(isi[k].size() > isi[f].size()){ swap(k, f); } for(auto y : isi[k]){ for(auto j : que[y]){ int fp = fpar(j.first); if(fp == f){ ans[j.second] = max(ans[j.second], cursz); } } isi[f].push_back(y); } isi[k].clear(); par[k] = f; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; isi.resize(n+1); par.resize(n+1); for(int i = 1; i <= n; i++){ par[i] = i; isi[i] = {i}; } vector<vector<pair<int, int>>> g(n+1); for(int i = 0; i < m; i++){ int a, b, w; cin >> a >> b >> w; g[a].push_back({b, w}); g[b].push_back({a, w}); } int c; cin >> c; multiset<pair<int, int>> s; vector<bool> d(n+1); vector<int> dis(n+1, 1e18); for(int i = 0; i < c; i++){ int h; cin >> h; s.insert({0, h}); dis[h] = 0; } while(s.size() > 0){ auto [time, k] = *s.begin(); s.erase(s.begin()); if(d[k]) continue; d[k] = true; for(auto[a, b] : g[k]){ if(d[a]) continue; if(dis[a] > time + b){ dis[a] = time+b; s.insert({dis[a], a}); } } } vector<int> srt = dis; sort(srt.begin(), srt.end()); srt.erase(unique(srt.begin(), srt.end()), srt.end()); reverse(srt.begin(), srt.end()); map<int, vector<int>> mp; for(int i = 1; i <= n; i++){ mp[dis[i]].push_back(i); } int q; cin >> q; que.resize(n+1); for(int i = 0; i < q; i++){ int a, b; cin >> a >> b; que[a].push_back({b, i}); que[b].push_back({a, i}); } ans.resize(q); for(auto i : srt){ cursz = i; for(auto y : mp[i]){ for(int z = 0; z < g[y].size(); z++){ if(dis[g[y][z].first] >= cursz){ merge(g[y][z].first, y); } } } } for(int i = 0; i < q; i++){ cout << ans[i] << "\n"; } return 0; }

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46