# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
450020 | vanic | 007 (CEOI14_007) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
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 !bio[0][c] && !bio[0][d];
}
int binary(){2
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;
}