Submission #551672

#	Time	Username	Problem	Language	Result	Execution time	Memory
551672		AugustinasJucas	007 (CEOI14_007)	C++14	23 / 100	1020 ms	25876 KiB

007

#include <bits/stdc++.h>
using namespace std;
const int dydis = 2e5 + 10;
const int inf = 1e9;
int n, m;
int s1, s2;
int gd, bd;
vector<int> gr[dydis];
int d1[dydis];
int d2[dydis];
void bfs(vector<int> start, int dist[]){
	for(int i = 1; i <= n; i++) {
		dist[i] = inf;
	}
	queue<int> q;
	for(auto &x : start) {
		q.push(x);
		dist[x] = 0;
	}
	while(q.size()) {
		int v = q.front();
		q.pop();
		for(auto &x : gr[v]) {
			if(dist[x] > dist[v] + 1) {
				dist[x] = dist[v] + 1;
				q.push(x);
			}
		}
	}
}
bool can(int wait) {
	bfs({bd}, d1);
	vector<int> pas;
	for(int i = 1; i <= n; i++) {
		if(d1[i] <= wait) {
			pas.push_back(i);
		}
	}
	//cout << "pas: "; for(auto &x : pas) cout << x << " ";
	//cout << endl;
	bfs(pas, d1);
	//cout << "tada d1[" << s1 << "] = " << d1[s1] << ", o d1[" << s2 << "] = " << d1[s2] << "\n";
	bool ret = (d2[s1] <= d1[s1] && d2[s2] <= d1[s2]);
	//cout << "can(" << wait << ") = " << ret << endl << endl;
	return ret;
}
int main () {
	cin >> n >> m;
	cin >> gd >> bd >> s1 >> s2;
	for(int i = 0; i < m; i++) {
		int a, b; cin >> a >> b; 
		gr[a].push_back(b);
		gr[b].push_back(a);
	}
	bfs({gd}, d2);
	
	int l = 0, mid; int r = n; int ans = -1;
	while(l <= r){
		mid = (l + r) / 2;
		if(can(mid)) {
			ans = mid;
			l = mid+1;
		}else {
			r = mid-1;
		}
	}
	cout << max(ans-1, -1);
	return 0;
}
/*
6 6
1 2 3 4
1 5
5 6
6 3
6 4
1 2
3 4

6 7
5 6 1 2
6 3
1 2
1 3
2 3
1 5
2 4
5 4
*/

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