Submission #413617

#	Time	Username	Problem	Language	Result	Execution time	Memory
413617		sinamhdv	007 (CEOI14_007)	C++11	93 / 100	271 ms	17676 KiB

007

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 200100
#define MAXE 600100

int n, m;
int s, d, a, b;
vector<int> adj[MAXN];
int h[3][MAXN];
bool mark[MAXN];
bool amark[2][MAXN], bmark[2][MAXN];
int ans;

void bfs(pii r, int *h)
{
	memset(mark, 0, sizeof(mark));
	queue<int> q;
	if (r.fr >= 0) mark[r.fr] = true, q.push(r.fr);
	if (r.sc >= 0) mark[r.sc] = true, q.push(r.sc);

	while (!q.empty())
	{
		int v = q.front(); q.pop();
		for (int u : adj[v])
		{
			if (mark[u]) continue;
			mark[u] = true;
			h[u] = h[v] + 1;
			q.push(u);
		}
	}
}

void findpars(int r, int *h, bool *mark)
{
	queue<int> q;
	q.push(r);
	mark[r] = true;
	while (!q.empty())
	{
		int v = q.front(); q.pop();
		for (int u : adj[v])
		{
			if (mark[u] || h[u] >= h[v]) continue;
			mark[u] = true;
			q.push(u);
		}
	}
}

int32_t main(void)
{
	fast_io;
	cin >> n >> m;
	cin >> s >> d >> a >> b;
	FOR(i, 0, m)
	{
		int x, y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}

	bfs({a, b}, h[0]);
	bfs({a, -1}, h[1]);
	bfs({b, -1}, h[2]);

	if (h[1][s] > h[1][d] || h[2][s] > h[2][d]) return cout << "-1\n", 0;

	ans = min(h[1][d] - h[1][s], h[2][d] - h[2][s]);
//	if (h[1][s] < h[1][d] || h[2][s] < h[2][d] || h[1][s] != h[2][s]) return cout << ans << endl, 0;

	findpars(s, h[1], amark[0]);
	findpars(s, h[2], bmark[0]);
	findpars(d, h[1], amark[1]);
	findpars(d, h[2], bmark[1]);

	int spy = h[0][s], doct = h[1][s];
	FOR(i, 1, n + 1)
	{
		if (amark[0][i] && bmark[0][i]) spy = min(spy, h[0][i]);
		if (amark[1][i] && bmark[1][i]) doct = min(doct, h[0][i]);
	}

	if (spy > doct) ans--;

	cout << ans << endl;

	return 0;
}

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