Submission #47262

#	Time	Username	Problem	Language	Result	Execution time	Memory
47262		jun6873	Evacuation plan (IZhO18_plan)	C++11	100 / 100	1442 ms	27336 KiB

plan

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

typedef pair<int, int> pint;
#define x first
#define y second

const int maxn = 100004, inf = 1e9 + 7;
int n, e, k, q, d[maxn], ans[maxn];
pint dp[maxn];
vector<pint> g[maxn];
priority_queue<pint, vector<pint>, greater<pint> > pq;
struct query {
	int i, l, r, x, y;
} a[maxn];

int p[maxn];
void dsu_init() { iota(p, p+maxn, 0); }
int root(int x) { return p[x]!=x ? p[x] = root(p[x]) : x; }
bool connect(int x, int y) {
	x = root(x); y = root(y);
	if (x==y) return false;
	p[x] = y;
	return true;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> n >> e;
	for (int i=0; i<e; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		g[x].emplace_back(y, z);
		g[y].emplace_back(x, z);
	}

	for (int i=1; i<=n; i++) d[i] = inf;
	cin >> k;
	for (int i=0; i<k; i++) {
		int x; cin >> x;
		d[x] = 0;
		pq.emplace(0, x);
	}

	while (!pq.empty()) {
		int nd = pq.top().x, nk = pq.top().y; pq.pop();
		if (d[nk] < nd) continue;
		for (pint i : g[nk]) if (nd + i.y < d[i.x]) {
			d[i.x] = nd + i.y;
			pq.emplace(nd + i.y, i.x);
		}
	}

	for (int i=0; i<n; i++) dp[i] = pint(d[i+1], i+1);
	sort(dp, dp+n);

	cin >> q;
	for (int i=0; i<q; i++) {
		int x, y;
		cin >> x >> y;
		a[i] = (query){i, 0, inf, x, y};
	}

	for (int _=0; _<31; _++) {
		sort(a, a+q, [](query a, query b) { return (a.l+a.r)/2 < (b.l+b.r)/2; });
		dsu_init();
		for (int i=q-1, j=n-1; ~i; i--) {
			int m = (a[i].l + a[i].r) / 2;
			while (j>=0 and dp[j].x >= m) {
				for (pint k : g[dp[j].y]) if (d[k.x] >= m) connect(dp[j].y, k.x);
				j--;
			}
			if (root(a[i].x) == root(a[i].y)) a[i].l = m;
			else a[i].r = m;
		}
	}

	for (int i=0; i<q; i++) ans[a[i].i] = a[i].l;
	for (int i=0; i<q; i++) cout << ans[i] << '\n';
}

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