제출 #907724

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
907724		daoquanglinh2007	Evacuation plan (IZhO18_plan)	C++17	100 / 100	752 ms	32468 KiB

plan

#include <bits/stdc++.h>
using namespace std;

#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 1e5, inf = 1e9+7, LIM = 1e8;

struct query{
	int id, s, t, l, r, mid;
};

int n, m, k, g[NM+5], q;
vector <pii> adj[NM+5];
priority_queue <pii, vector <pii>, greater <pii> > Q;
int d[NM+5], a[NM+5];
bool fix[NM+5];
query b[NM+5];
int ans[NM+5];
int parent[NM+5], sz[NM+5];
bool on[NM+5];

void dijkstra(){
	for (int i = 1; i <= n; i++) d[i] = +inf;
	for (int i = 1; i <= k; i++){
		d[g[i]] = 0;
		Q.push(mp(0, g[i]));
	}
	while (true){
		while (!Q.empty() && fix[Q.top().se]) Q.pop();
		if (Q.empty()) break;
		int u = Q.top().se; Q.pop();
		fix[u] = 1;
		for (pii _ : adj[u]){
			int v = _.fi, w = _.se;
			if (fix[v]) continue;
			if (d[u]+w < d[v]){
				d[v] = d[u]+w;
				Q.push(mp(d[v], v));

			}
		}
	}
	for (int i = 1; i <= n; i++) a[i] = i;
	sort(a+1, a+1+n, [&](int x, int y){
		return d[x] > d[y];
	});
}

bool cmp(query a, query b){
	if (a.l > a.r) return 0;
	if (b.l > b.r) return 1;
	return a.mid > b.mid;
}

void make_set(int v){
	parent[v] = v;
	sz[v] = 1;
}

int find_set(int v){
	return parent[v] == v ? v : parent[v] = find_set(parent[v]);
}

void union_sets(int u, int v){
	u = find_set(u), v = find_set(v);
	if (u == v) return;
	if (sz[u] < sz[v]) swap(u, v);
	parent[v] = u;
	sz[u] += sz[v]; 
}

void parallel_binary_search(){
	for (int i = 1; i <= q; i++)
		b[i].mid = (b[i].l+b[i].r)/2;
	sort(b+1, b+1+q, cmp);
	
	for (int i = 1; i <= n; i++){
		make_set(i);
		on[i] = 0;
	}
	int j = 1;
	for (int i = 1; i <= q; i++){
		if (b[i].l > b[i].r) break;
		while (j <= n && d[a[j]] >= b[i].mid){
			on[a[j]] = 1;
			for (pii _ : adj[a[j]]){
				int v = _.fi;
				if (on[v]) union_sets(a[j], v);
			}
			j++;
		}
		if (on[b[i].s] && on[b[i].t] && find_set(b[i].s) == find_set(b[i].t)){
			ans[b[i].id] = b[i].mid;
			b[i].l = b[i].mid+1;
		}
		else b[i].r = b[i].mid-1;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m;
	while (m--){
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back(mp(v, w));
		adj[v].push_back(mp(u, w));
	}
	cin >> k;
	for (int i = 1; i <= k; i++) cin >> g[i];
	dijkstra();
	
	cin >> q;
	for (int i = 1; i <= q; i++){
		cin >> b[i].s >> b[i].t;
		b[i].id = i;
		b[i].l = 1, b[i].r = LIM;
	}
	for (int i = 1; (1<<i) < 2*LIM; i++){
		parallel_binary_search();
	}
	
	for (int i = 1; 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