Submission #1094133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094133		xnqs	Evacuation plan (IZhO18_plan)	C++17	100 / 100	636 ms	32676 KiB

plan

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>

class DSU {
private:
	int n;
	std::vector<int> t;
	std::vector<int> sz;
public:
	DSU(int n = 0): n(n) {
		t.assign(n,0); std::iota(t.begin(),t.end(),0);
		sz.assign(n,1);
	}

	int Find(int k) {
		if (t[k]==k) return t[k];
		return t[k] = Find(t[k]);
	}

	int Unite(int a, int b) {
		int ra = Find(a);
		int rb = Find(b);
		if (ra==rb) {
			return 0;
		}

		if (sz[ra]<sz[rb]) {
			std::swap(ra,rb);
		}

		sz[ra] += sz[rb];
		t[rb] = ra;
		return 1;
	}
};

struct Query {
	int a, b, l, r, m, idx;
	Query(int a, int b, int idx):
		a(a), b(b), l(0), r(1000000000), m(500000000), idx(idx) {}
};

int gs, edg;
std::vector<std::vector<std::pair<int,int>>> adj_list;
int danger[100005];
int ans[100005];

void dijkstra() {
	std::fill(danger,danger+100005,0x3f3f3f3f);
	std::priority_queue<std::pair<int,int>, std::vector<std::pair<int,int>>, std::greater<std::pair<int,int>>> q;

	int z;
	std::cin >> z;
	while (z--) {
		int k;
		std::cin >> k;
		danger[k] = 0;
		q.emplace(0,k);
	}

	while (!q.empty()) {
		int k = q.top().second;
		q.pop();

		for (const auto& [i, w] : adj_list[k]) {
			if (danger[i]>danger[k]+w) {
				danger[i] = danger[k]+w;
				q.emplace(danger[i],i);
			}
		}
	}
}

int main() {
	std::cin >> gs >> edg;
	adj_list.resize(gs+1);
	for (int i = 0, a, b, c; i < edg; i++) {
		std::cin >> a >> b >> c;
		adj_list[a].emplace_back(b,c);
		adj_list[b].emplace_back(a,c);
	}

	dijkstra();

	int q;
	std::cin >> q;
	std::vector<Query> queries;
	for (int i = 0, a, b; i < q; i++) {
		std::cin >> a >> b;
		queries.emplace_back(a,b,i);
	}

	std::vector<int> nodes;
	for (int i = 1; i <= gs; i++) {
		nodes.emplace_back(i);
	}
	std::sort(nodes.begin(),nodes.end(),[&](int a, int b) {
		return danger[a] < danger[b];
	});

	for (int iter = 0; iter < 30; iter++) {
		std::sort(queries.begin(),queries.end(),[](const Query& a, const Query& b) {
			return a.m > b.m;
		});

		int scl = gs-1;
		DSU dsu(gs+1);
		std::vector<bool> activated(gs+1,0);
		for (auto& [a, b, ql, qr, qm, qidx] : queries) {
			//std::cout << a << " " << b << " " << ql << " " << qr << " " << qm << " " << qidx << "\n";
			if (ql>qr) {
				continue;
			}

			while (scl>=0&&danger[nodes[scl]]>=qm) {
				for (const auto& [i, w] : adj_list[nodes[scl]]) {
					if (activated[i]) {
						dsu.Unite(nodes[scl],i);
					}
				}
				activated[nodes[scl]] = 1;
				--scl;
			}

			if (activated[a] && activated[b] && dsu.Find(a) == dsu.Find(b)) {
				ans[qidx] = qm;
				ql = qm+1;
			}
			else {
				qr = qm-1;
			}
			qm = (ql+qr)>>1;
		}
	}

	for (int i = 0; i < q; i++) {
		std::cout << ans[i] << "\n";
	}
}

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