Submission #41165

#	Time	Username	Problem	Language	Result	Execution time	Memory
41165		aome	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1605 ms	33108 KiB

plan

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

typedef pair<int, int> ii;

int n, m, k, q;
int a[N], dis[N];
int x[N], y[N];
int l[N], r[N];
int par[N];
vector<ii> G[N];
vector<ii> vec;
vector<int> queries[N];

int find(int u) { return par[u] == u ? u : par[u] = find(par[u]); }

void join(int u, int v) { par[find(u)] = find(v); }

void dijkstra() {
	for (int i = 1; i <= n; ++i) dis[i] = 1e9;
	priority_queue< ii, vector<ii>, greater<ii> > pq;
	for (int i = 1; i <= k; ++i) {
		pq.push(ii(0, a[i])), dis[a[i]] = 0;
	}
	while (pq.size()) {
		ii u = pq.top(); pq.pop();
		if (u.first != dis[u.second]) continue;
		for (auto v : G[u.second]) {
			v.first += u.first;
			if (v.first < dis[v.second]) {
				dis[v.second] = v.first, pq.push(v);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int u, v, w; cin >> u >> v >> w;
		G[u].push_back(ii(w, v)), G[v].push_back(ii(w, u));
	}
	cin >> k;
	for (int i = 1; i <= k; ++i) cin >> a[i];
	dijkstra();
	vec.push_back(ii(1e9, 0));
	for (int i = 1; i <= n; ++i) vec.push_back(ii(dis[i], i));
	sort(vec.begin(), vec.end(), greater<ii>());
	cin >> q;
	for (int i = 1; i <= q; ++i) {
		cin >> x[i] >> y[i];
		l[i] = 1, r[i] = n;
	}
	while (1) {
		bool found = 0;
		for (int i = 1; i <= q; ++i) found |= l[i] < r[i];
		if (!found) break;
		for (int i = 1; i <= n; ++i) par[i] = i;
		for (int i = 1; i <= n; ++i) queries[i].clear();
		for (int i = 1; i <= q; ++i) {
			queries[(l[i] + r[i]) / 2].push_back(i);
		}
		for (int i = 1; i <= n; ++i) {
			for (auto j : G[vec[i].second]) {
				if (dis[j.second] >= dis[vec[i].second]) join(vec[i].second, j.second);
			}
			for (auto j : queries[i]) {
				if (find(x[j]) == find(y[j])) r[j] = (l[j] + r[j]) / 2;
				else l[j] = (l[j] + r[j]) / 2 + 1;
			}
		}
	}
	for (int i = 1; i <= q; ++i) cout << vec[l[i]].first << '\n';
}

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