Submission #450094

#	Time	Username	Problem	Language	Result	Execution time	Memory
450094		vanic	007 (CEOI14_007)	C++14	30 / 100	1097 ms	16520 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];
bool bio[2][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]);
			}
		}
	}
}

void siri(int x, int y, int z){
	bio[y][z][x]=1;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(dist[y][ms[x][i]]==dist[y][x]-1){
			siri(ms[x][i], y, z);
		}
	}
}
 
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{
		if(dist[0][c]-dist[1][c]==dist[0][d]-dist[1][d]){
			siri(c, 0, 0);
			siri(d, 0, 1);
			siri(c, 1, 0);
			siri(d, 1, 1);
			int mini[2]={(int)1e9, (int)1e9};
			int cvor[2];
			int val;
			for(int j=0; j<2; j++){
				for(int i=0; i<n; i++){
					if(bio[j][0][i] && bio[j][1][i]){
						val=dist[j][c]-dist[j][i];
						if(val<mini[j]){
							mini[j]=val;
							cvor[j]=i;
						}
						
					}
				}
			}
			int raz=dist[1][c]-dist[0][c];
			if(cvor[0]==cvor[1]){
				cout << raz << '\n';
			}
			else{
				if(mini[0]<=mini[1]){
					cout << raz << '\n';
				}
				else{
					cout << raz-1 <<  '\n';
				}
			}
		}
		else{
			cout << min(dist[1][c]-dist[0][c], dist[1][d]-dist[0][d]) << '\n';
		}
	}
	return 0;
}

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