Submission #501360

#	Time	Username	Problem	Language	Result	Execution time	Memory
501360		NachoLibre	Evacuation plan (IZhO18_plan)	C++17	100 / 100	576 ms	36868 KiB

plan

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;

const int N = 100005, M = 17;
vector<int> dyup(N, -1);
int up[N][M];
int P(int x) {
	return dyup[x] < 0 ? x : dyup[x] = P(dyup[x]);
}
void H(int x, int y) {
	if(P(y) == x) return;
	up[P(y)][0] = x;
	dyup[P(y)] = x;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	#ifdef wambule
	freopen("Untitledfile.txt", "r", stdin);
	#endif
	int n, m;
	cin >> n >> m;
	vector<array<int, 2>> v1[n + 1];
	for(int i = 1; i <= m; ++i) {
		int x, y, z;
		cin >> x >> y >> z;
		v1[x].push_back({y, z});
		v1[y].push_back({x, z});
	}
	int k;
	cin >> k;
	set<array<int, 2>> s1;
	vector<int> d(n + 1, -1);
	for(int i = 1; i <= k; ++i) {
		int x;
		cin >> x;
		s1.insert({0, x});
		d[x] = 0;
	}
	while(s1.size()) {
		int x = (*s1.begin())[1];
		s1.erase(s1.begin());
		for(auto y : v1[x]) {
			if(d[y[0]] == -1 || d[y[0]] > d[x] + y[1]) {
				if(d[y[0]] != -1) s1.erase({d[y[0]], y[0]});
				d[y[0]] = d[x] + y[1];
				s1.insert({d[y[0]], y[0]});
			}
		}
	}
	vector<array<int, 2>> v2;
	for(int i = 1; i <= n; ++i) {
		v2.push_back({d[i], i});
	}
	sort(all(v2));
	reverse(all(v2));
	vector<bool> cc(n + 1);
	for(auto x : v2) {
		cc[x[1]] = 1;
		for(auto y : v1[x[1]]) {
			if(!cc[y[0]]) continue;
			H(x[1], y[0]);
		}
	}
	for(int j = 1; j < M; ++j) {
		for(int i = 1; i <= n; ++i) {
			up[i][j] = up[up[i][j - 1]][j - 1];
		}
	}
	vector<int> dt(n + 1);
	for(int i = 1; i <= n; ++i) {
		int x = i;
		for(int j = M - 1; j >= 0; --j) {
			if(up[x][j] != 0) {
				x = up[x][j];
				dt[i] |= (1 << j);
			}
		}
	}
	int q;
	cin >> q;
	for(int i = 1; i <= q; ++i) {
		int x, y;
		cin >> x >> y;
		if(dt[x] < dt[y]) { swap(x, y); }
		for(int j = M - 1; j >= 0; --j) {
			if(dt[x] - (1 << j) >= dt[y]) {
				x = up[x][j];
			}
		}
		int ap = 0;
		if(x == y) {
			ap = d[x];
		} else {
			for(int j = M - 1; j >= 0; --j) {
				if(up[x][j] != up[y][j]) {
					x = up[x][j];
					y = up[y][j];
				}
			}
			ap = d[up[x][0]];
		}
		cout << ap << "\n";
	}
	return 0;
}

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