Submission #84001

#	Time	Username	Problem	Language	Result	Execution time	Memory
84001		Saboon	007 (CEOI14_007)	C++17	93 / 100	327 ms	17488 KiB

007

#include <bits/stdc++.h>
#define MP make_pair
#define F first
#define PB push_back
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int maxn = 2e5 + 4;

vector <int> g[maxn];
int dis[maxn][2];
int h[maxn];

int maximal_path (int v) {
	memset (h, -1, sizeof h);
	int ret = 0;
	queue <int> q;
	q.push(v);
	h[v] = 0;
	while (!q.empty()) {
		v = q.front();
		q.pop();
		ret = max (ret, h[v]);
		for (auto u : g[v]) {
			if (h[u] == -1 and dis[u][0] < dis[v][0] and dis[u][1] < dis[v][1]) {
				h[u] = h[v] + 1;
				q.push (u);
			}
		}
	}
	return ret;
}

void bfs (int src, bool wh) {
	queue <int> q;
	q.push(src);
	dis[src][wh] = 0;
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		for (auto u : g[v]) {
			if (dis[u][wh] == -1) {
				dis[u][wh] = dis[v][wh] + 1;
				q.push(u);
			}
		}
	}
}

int main (){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	int s, t, a, b;
	cin >> s >> t >> a >> b;
	for (int e = 0; e < m; e ++) {
		int v, u;
		cin >> v >> u;
		g[v].PB(u);
		g[u].PB(v);
	}

	memset (dis, -1, sizeof dis);
	bfs (a, 0);
	bfs (b, 1);
	int ans;
	if (dis[t][0] < dis[s][0])
		ans = -1;
	else
		ans = dis[t][0] - dis[s][0];
	
	if (dis[t][1] < dis[s][1])
		ans = -1;
	else
		ans = min (ans, dis[t][1] - dis[s][1]);
	if (ans == -1)
		return cout << -1 << endl, 0;
	if (dis[s][0] == dis[s][1] and maximal_path(t) > maximal_path(s) + ans)
		ans --;
	return cout << ans << endl, 0;
}

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