Submission #449998

#	Time	Username	Problem	Language	Result	Execution time	Memory
449998		vanic	007 (CEOI14_007)	C++14	0 / 100	1092 ms	15252 KiB

007

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
#include <cassert>
#include <set>
#include <array>

using namespace std;

const int maxn=2e5+5;

vector < int > ms[maxn];
int a, b, c, d;
bool bio[2][maxn];
int n, m;


bool provjeri(int x){
	set < array < int, 3 > > s;
	memset(bio, 0, sizeof(bio));
	s.insert({0, 0, b});
	s.insert({x, 1, a});
	array < int, 3 > y;
	while(!s.empty()){
		y=*s.begin();
		s.erase(s.begin());
		if(!y[1] && bio[1][y[2]]){
			continue;
		}
		if(!y[1] && (y[2]==c || y[2]==d)){
			return 0;
		}
		bio[y[1]][y[2]]=1;
		for(int i=0; i<(int)ms[y[2]].size(); i++){
			if(!bio[y[1]][ms[y[2]][i]]){
				bio[y[1]][ms[y[2]][i]]=1;
				s.insert({y[0]+1, y[1], ms[y[2]][i]});
			}
		}
	}
	return 1;
}

int binary(){
	int lo=-1, hi=n, mid;
	while(lo<hi){
		mid=(lo+hi+1)/2;
		if(provjeri(mid)){
			lo=mid;
		}
		else{
			hi=mid-1;
		}
	}
	return lo;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	cin >> a >> b >> c >> d;
	a--; b--; c--; d--;
	assert(a!=b && a!=c && a!=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);
	}
	cout << binary() << '\n';
	return 0;
}

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