제출 #885391

#제출 시각아이디문제언어결과실행 시간메모리
885391jcelinEvacuation plan (IZhO18_plan)C++14
0 / 100
452 ms63040 KiB
#include <bits/stdc++.h> //#include<ext/pb_ds/assoc_container.hpp> //#include<ext/pb_ds/tree_policy.hpp> using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef long double ld; #define ii pair<int,int> #define pll pair<ll,ll> #define vi vector<int> #define vii vector<ii> #define vll vector<ll> #define vpll vector<pll> #define msi multiset<int> #define si set<int> #define PB push_back #define PF push_front #define PPB pop_back #define PPF pop_front #define X first #define Y second #define MP make_pair #define FOR(i, a, b) for (int i = int(a); i < int(b); i++) #define REP(i, n) FOR(i, 0, n) #define all(x) (x).begin(), (x).end() const int mod = 1e9 + 7; const int MOD = 998244353; const int inf = 1e9 + 7; const ll INF = 1e18 + 7; const int logo = 30; const int MAXN = 1e6 + 2; const int off = 1 << logo; const int trsz = off << 1; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, -1, 1}; struct uf{ int par[MAXN], sz[MAXN]; void init(int n){ for(int i=1; i<=n; i++) par[i] = i, sz[i] = 1; } int find(int x){ return par[x] == x ? x : par[x] = find(par[x]); } void unite(int a, int b){ a = find(a), b = find(b); if(a == b) return; if(sz[a] < sz[b]) swap(a, b); par[b] = a; sz[a] += sz[b]; } bool query(int a, int b){ return find(a) == find(b); } }uf; int lo[MAXN], hi[MAXN], dis[MAXN], cj, n, m, q, st[MAXN], en[MAXN], ans[MAXN]; vii g[MAXN]; vector<pair<int, ii>> brid; vi qs; bool cmp(int a, int b){ return lo[a] > lo[b]; } void paralelni(){ sort(all(qs), cmp); cj = 0; uf.init(n); for(auto &x : qs){ if(lo[x] > hi[x]) continue; int mid = (lo[x] + hi[x]) / 2; while(cj < (int)brid.size() and brid[cj].X >= mid) uf.unite(brid[cj].Y.X, brid[cj].Y.Y), cj++; if(uf.query(st[x], en[x])) lo[x] = mid + 1, ans[x] = mid; else hi[x] = mid - 1; } } void dijkstra(){ set<ii> s; for(int i=1; i<=n; i++) s.insert({dis[i], i}); while(!s.empty()){ ii cur = *s.begin(); s.erase(s.begin()); int u = cur.Y, d = cur.X; for(auto &x : g[u]){ int nd = d + x.Y; if(nd < dis[x.X]){ s.erase({dis[x.X], x.X}); dis[x.X] = nd; s.insert({dis[x.X], x.X}); } } } for(int i=1; i<=n; i++){ for(auto &x : g[i]) if(dis[i] < dis[x.X]) brid.PB({dis[i], {i, x.X}}); } sort(all(brid)); reverse(all(brid)); } void solve(){ cin >> n >> m; for(int i=1; i<=m; i++){ int a, b, w; cin >> a >> b >> w; g[a].PB({b, w}); g[b].PB({a, w}); } int k; cin >> k; for(int i=1; i<=n; i++) dis[i] = inf; for(int i=1, x; i<=k; i++) cin >> x, dis[x] = 0; dijkstra(); cin >> q; for(int i=0; i<q; i++){ cin >> st[i] >> en[i]; lo[i] = 0, hi[i] = inf, ans[i] = inf; qs.PB(i); } for(int i=0; i<32; i++) paralelni(); for(int i=0; i<q; i++) cout << ans[i] << "\n"; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solve(); 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...