Submission #551679

#	Time	Username	Problem	Language	Result	Execution time	Memory
551679		AugustinasJucas	007 (CEOI14_007)	C++14	100 / 100	953 ms	21556 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);
		}
	}
	bfs(pas, d1);
	bool ret = (d2[s1] <= d1[s1] && d2[s2] <= d1[s2]);
	return ret;
}
int dp1[dydis] = {};
int dp2[dydis] = {};
int when(int dist[]){ 
	vector<pair<int, int> > vec;
	for(int i = 1; i <= n; i++) {
		vec.push_back({dist[i], i});
	}
	sort(vec.begin(), vec.end());
	reverse(vec.begin(), vec.end());
	int ret = 0;
	for(int i = 0; i < n; i++) {
		int v = vec[i].second;
		dp1[v] = (v == s1);
		dp2[v] = (v == s2);
		for(auto x : gr[v]) {
			if(dist[x] != dist[v] + 1) continue;
			dp1[v] |= dp1[x];
			dp2[v] |= dp2[x];
		}
		if(dp1[v] && dp2[v]) ret = max(ret, dist[v]);
	}
	return ret;
}
int main () {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	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;
		}
	}
	
	if(ans == -1) {
		cout << ans;
		return 0;
	}
	can(ans);
	
	if(d1[s1] != d1[s2]) {
		cout << ans;
		return 0;
	}
	if(d2[s1] != d2[s2]) {
		cout << ans;
		return 0;
	}
	
	int kadaBlogas = when(d1);
	int kadaGeras = when(d2);
	
	ans -= (kadaGeras < kadaBlogas);
	cout << ans;
	
	return 0;
}

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