Submission #1236780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236780		kaiboy	007 (CEOI14_007)	C++20	100 / 100	131 ms	17512 KiB

007

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int N = 200000;

vector<int> ej[N];
int dd0[N], dd1[N], dd[N], qu[N];

void bfs(int r, int *dd, int n) {
	for (int i = 0; i < n; i++)
		dd[i] = n;
	int cnt = 0; dd[qu[cnt++] = r] = 0;
	for (int h = 0; h < cnt; h++) {
		int i = qu[h], d = dd[i] + 1;
		for (int j : ej[i])
			if (dd[j] == n)
				dd[qu[cnt++] = j] = d;
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, m; cin >> n >> m;
	int t0, t1, s0, s1; cin >> t0 >> t1 >> s0 >> s1, t0--, t1--, s0--, s1--;
	while (m--) {
		int i, j; cin >> i >> j, i--, j--;
		ej[i].push_back(j);
		ej[j].push_back(i);
	}
	bfs(s0, dd0, n), bfs(s1, dd1, n);
	if (dd0[t0] > dd1[t0])
		for (int i = 0; i < n; i++)
			swap(dd0[i], dd1[i]);
	if (dd0[t0] < dd1[t0]) {
		if (dd0[t1] < dd1[t1])
			cout << max(dd0[t1] - dd0[t0], -1) << '\n';
		else
			cout << max(dd1[t1] - dd1[t0], -1) << '\n';
		return 0;
	}
	if (dd0[t1] > dd1[t1])
		for (int i = 0; i < n; i++)
			swap(dd0[i], dd1[i]);
	if (dd0[t1] < dd1[t1]) {
		cout << max(dd0[t1] - dd0[t0], -1) << '\n';
		return 0;
	}
	bfs(t0, dd, n);
	int d0 = n;
	for (int i = 0; i < n; i++)
		if (dd0[i] == dd1[i] && dd0[i] + dd[i] == dd0[t0])
			d0 = min(d0, dd0[i]);
	bfs(t1, dd, n);
	int d1 = n;
	for (int i = 0; i < n; i++)
		if (dd0[i] == dd1[i] && dd0[i] + dd[i] == dd0[t1])
			d1 = min(d1, dd0[i]);
	if (d0 <= d1)
		cout << max(dd0[t1] - dd0[t0], -1) << '\n';
	else
		cout << max(dd0[t1] - dd0[t0] - 1, -1) << '\n';
	return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70