Submission #82369

#	Time	Username	Problem	Language	Result	Execution time	Memory
82369		Dat160601	007 (CEOI14_007)	C++17	100 / 100	275 ms	17532 KiB

007

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int read(){
	char p;
	while((p = getchar())){
		if(p < '0' || p > '9') continue;
		break;
	}
	int ret = p - '0';
	while((p = getchar())){
		if(p >= '0' && p <= '9'){
			ret *= 10;
			ret += p - '0';
		}
		else break;
	}
	return ret;
}

int n, m, u, v;
int s, d, a, b, disa[200007], disb[200007], dist[200007];
bool vis[200007];
queue <int> q;
vector <int> edge[200007];

int go(int st){
	memset(dist, 0, sizeof(dist));
	memset(vis, false, sizeof(vis));
	int res = 0;
	q.push(st);
	vis[st] = true;
	while(!q.empty()){
		u = q.front();
		q.pop();
		res = max(res, dist[u]);
		for(int v : edge[u]){
			if(vis[v]) continue;
			if(disa[u] == disa[v] + 1 && disb[u] == disb[v] + 1){
				vis[v] = true;
				dist[v] = dist[u] + 1;
				q.push(v);
			}
		}
	}
	return res;
}

int main(){
	n = read(), m = read();
	s = read(), d = read(), a = read(), b = read();
	for(int i = 1; i <= m; i++){
		u = read();
		v = read();
		edge[u].pb(v);
		edge[v].pb(u);
	}
	vis[a] = true;
	q.push(a);
	while(!q.empty()){
		u = q.front();
		q.pop();
		for(int v : edge[u]){
			if(vis[v]) continue;
			vis[v] = true;
			disa[v] = disa[u] + 1;
			q.push(v);
		}
	}
	memset(vis, false, sizeof(vis));
	vis[b] = true;
	q.push(b);
	while(!q.empty()){
		u = q.front();
		q.pop();
		for(int v : edge[u]){
			if(vis[v]) continue;
			vis[v] = true;
			disb[v] = disb[u] + 1;
			q.push(v);
		}
	}
	int cal_a = disa[d] - disa[s];
	int cal_b = disb[d] - disb[s];
	//cout << cal_a << " " << cal_b << endl;
	if(min(cal_a, cal_b) < 0){
		printf("-1");
		return 0;
	}
	if(cal_a != cal_b){
		cal_a = min(cal_a, cal_b);
		cout << cal_a;
		return 0;
	}
	int down_s = go(s), down_d = go(d);
	if(cal_a + down_s < down_d) cal_a--;
	if(cal_a < 0) cout << -1;
	else cout << cal_a;
}

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