Submission #760557

#	Time	Username	Problem	Language	Result	Execution time	Memory
760557		NK_	Evacuation plan (IZhO18_plan)	C++17	100 / 100	727 ms	35680 KiB

plan

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

#define f first
#define s second
#define mp make_pair

using pi = pair<int, int>;

template<class T> using V = vector<T>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;

const int INF = 1e9+10;

struct DSU {
	V<int> e; void init(int N) { e = V<int>(N, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool conn(int x, int y) { return get(x) == get(y); }
	bool unite(int x, int y) {
		x = get(x), y = get(y); if (x == y) return 0;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y]; e[y] = x; return 1;
	}
};


int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M; cin >> N >> M;

	V<V<pi>> adj(N);

	for(int i = 0; i < M; i++) {
		int u, v, w; cin >> u >> v >> w; --u, --v;
		adj[u].pb(mp(v, w));
		adj[v].pb(mp(u, w));
	}

	pq<pi> q; 

	V<int> dst(N, INF), vis(N, 0);

	int NPP; cin >> NPP;
	for(int i = 0; i < NPP; i++) {
		int x; cin >> x; --x;
		dst[x] = 0; q.push(mp(dst[x], x));
	}

	while(sz(q)) {
		int u = q.top().s; q.pop();

		if (vis[u]) continue;
		vis[u] = 1;

		for(auto e : adj[u]) {
			int v, w; tie(v, w) = e;
			if (dst[v] > dst[u] + w) {
				dst[v] = dst[u] + w;
				q.push(mp(dst[v], v));
			}
		}
	}

	// PARALLEL BINSEARCH ??!?!?!?!??!?!?!?!?!?
	// I DONT KNOW WHAT I AM DOING

	int Q; cin >> Q;
	V<pi> X(Q); for(auto& x : X) { cin >> x.f >> x.s; --x.f, --x.s; }

	V<int> lo(Q, 0), hi(Q, N);

	V<int> ord(N); iota(begin(ord), end(ord), 0); 
	sort(begin(ord), end(ord), [&](int x, int y) {
		return dst[x] > dst[y];
	});

	while(1) {
		// cout << t << endl;
		bool DONE = 1;
		V<V<int>> E(N); 

		for(int i = 0; i < Q; i++) if (lo[i] < hi[i]) {
			int mid = (lo[i] + hi[i]) / 2; 
			// cout << i << " => " << lo[i] << " , " << hi[i] << endl;
			E[mid].pb(i);
			DONE = 0;
		}

		if (DONE) break;

		DSU D; D.init(N);
		for(int mid = 0; mid < N; mid++) {
			int u = ord[mid];
			// cout << mid << " => " << u << " - " << dst[u] << endl;
			for(auto e : adj[u]) {
				int v = e.f;
				if (dst[v] >= dst[u]) D.unite(v, u);
			}

			for(auto i : E[mid]) {
				if (D.conn(X[i].f, X[i].s)) hi[i] = mid;
				else lo[i] = mid + 1;
			}
		}
		// cout << endl << endl;
	}

	V<int> ans(Q); for(int i = 0; i < Q; i++) {
		// cout << i << " => " << lo[i] << " , " << hi[i] << endl;
		ans[i] = dst[ord[lo[i]]];
	}

	for(auto x : ans) cout << x << nl;


    return 0;
}

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