Submission #374897

#	Time	Username	Problem	Language	Result	Execution time	Memory
374897		SeDunion	Evacuation plan (IZhO18_plan)	C++17	100 / 100	2480 ms	103916 KiB

plan

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;
 
vector<pair<int,int>>g[N];
 
int d[N], s[N], t[N], l[N], r[N], p[N];
 
int get(int x) {
	if (x == p[x]) return x;
	return p[x] = get(p[x]);
}
 
vector<int>ask[N];
 
vector<int>add[N];
 
int sq[N];
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1 ; i <= m ; ++ i) {
		int a, b, w;
		cin >> a >> b >> w;
		g[a].emplace_back(b, w);
		g[b].emplace_back(a, w);
	}
	for (int i = 1 ; i <= n ; ++ i) {
		d[i] = int(1e9+123);
	}
	int k;
	cin >> k;
	set<pair<int,int>>S;
	for (int i = 1 ; i <= k ; ++ i) {
		int x;
		cin >> x;
		d[x] = 0;
		S.insert({0, x});
	}
	while(S.size()) {
		int v = S.begin()->second; S.erase(S.begin());
		for (auto [to, w] : g[v]) if (d[to] > d[v] + w) {
			S.erase({d[to], to});
			d[to] = d[v] + w;
			S.insert({d[to], to});
		}
	}
	for (int i = 1 ; i <= n ; ++ i) {
		//cout << d[i] << " \n"[i == n];
	}
	vector<int>vals;
	for (int i = 1 ; i <= n ; ++ i) {
		vals.emplace_back(d[i]);
	}
	sort(vals.begin(), vals.end()), vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
	for (int i = 1 ; i <= n ; ++ i) {
		sq[i] = lower_bound(vals.begin(), vals.end(), d[i]) - vals.begin();
		add[sq[i]].emplace_back(i);
	}
	int q;
	cin >> q;
	for (int i = 1 ; i <= q ; ++ i) {
		cin >> s[i] >> t[i];
		l[i] = 0, r[i] = (int)vals.size() - 1;
	}
	for (int rep = 0 ; rep < 30 ; ++ rep) {
		for (int i = 0 ; i < N ; ++ i) {
			ask[i].clear();
		}
		for (int i = 1 ; i <= q ; ++ i) {
			if (l[i] < r[i]) {
				int m = (l[i] + r[i] + 1) / 2;
				ask[m].emplace_back(i);
			}
		}
		for (int i = 1 ; i <= n ; ++ i) {
			p[i] = i;
		}
		for (int i = (int)vals.size() - 1 ; i >= 0 ; -- i) {
			for (int v : add[i]) {
				for (auto [to, w] : g[v]) {
					if (d[to] >= vals[i]) {
						p[get(v)] = get(to);
					}
				}
			}
			for (auto j : ask[i]) {
				if (get(s[j]) == get(t[j])) {
					l[j] = i;
				} else {
					r[j] = i - 1;
				}
			}
		}
	}
	for (int i = 1 ; i <= q ; ++ i) {
		cout << vals[l[i]] << "\n";
	}
}

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