Submission #449603

#	Time	Username	Problem	Language	Result	Execution time	Memory
449603		vanic	007 (CEOI14_007)	C++14	0 / 100	264 ms	23572 KiB

007

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

const int maxn=2e5+5;

vector < int > ms[maxn];
int dist[2][maxn];

void bfs(int x, int ind){
	queue < int > q;
	q.push(x);
	dist[ind][x]=0;
	while(!q.empty()){
		x=q.front();
		q.pop();
		for(int i=0; i<(int)ms[x].size(); i++){
			if(dist[ind][ms[x][i]]==-1){
				dist[ind][ms[x][i]]=dist[ind][x]+1;
				q.push(ms[x][i]);
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(dist, -1, sizeof(dist));
	int n, m;
	cin >> n >> m;
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	a--; b--; c--; d--;
	int x, y;
	for(int i=0; i<m; i++){
		cin >> x >> y;
		x--; y--;
		ms[x].push_back(y);
		ms[y].push_back(x);
	}
	bfs(a, 0);
	bfs(b, 1);
	if(dist[0][c]>dist[1][c] || dist[0][d]>dist[1][d]){
		cout << -1 << '\n';
	}
	else{
		cout << min(dist[1][c]-dist[0][c], dist[1][d]-dist[0][d]) << '\n';
	}
	return 0;
}

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