oj.uz

Submission #551679

# Submission time Handle Problem Language Result Execution time Memory
551679 2022-04-21T10:17:43 Z AugustinasJucas 007 (CEOI14_007) C++14
100 / 100
 953 ms 21556 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5020 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 ms 5128 KB Output is correct
13 Correct 4 ms 5076 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Correct 4 ms 5076 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 4 ms 5076 KB Output is correct
20 Correct 4 ms 5076 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 4 ms 5076 KB Output is correct
23 Correct 3 ms 5076 KB Output is correct
24 Correct 4 ms 5076 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 7772 KB Output is correct
2 Correct 121 ms 8944 KB Output is correct
3 Correct 82 ms 7796 KB Output is correct
4 Correct 180 ms 8924 KB Output is correct
5 Correct 72 ms 7016 KB Output is correct
6 Correct 77 ms 7308 KB Output is correct
7 Correct 109 ms 8248 KB Output is correct
8 Correct 109 ms 8204 KB Output is correct
9 Correct 174 ms 8728 KB Output is correct
10 Correct 341 ms 13140 KB Output is correct
11 Correct 273 ms 10948 KB Output is correct
12 Correct 326 ms 12168 KB Output is correct
13 Correct 308 ms 11292 KB Output is correct
14 Correct 139 ms 9204 KB Output is correct
15 Correct 295 ms 12316 KB Output is correct
16 Correct 307 ms 11256 KB Output is correct
17 Correct 302 ms 12200 KB Output is correct
18 Correct 285 ms 11932 KB Output is correct
19 Correct 405 ms 13500 KB Output is correct
20 Correct 483 ms 16068 KB Output is correct
21 Correct 554 ms 15932 KB Output is correct
22 Correct 410 ms 14648 KB Output is correct
23 Correct 544 ms 13092 KB Output is correct
24 Correct 650 ms 15884 KB Output is correct
25 Correct 579 ms 15388 KB Output is correct
26 Correct 447 ms 12212 KB Output is correct
27 Correct 657 ms 15856 KB Output is correct
28 Correct 695 ms 15792 KB Output is correct
29 Correct 573 ms 16148 KB Output is correct
30 Correct 599 ms 16960 KB Output is correct
31 Correct 726 ms 17276 KB Output is correct
32 Correct 648 ms 15740 KB Output is correct
33 Correct 530 ms 13416 KB Output is correct
34 Correct 784 ms 16380 KB Output is correct
35 Correct 568 ms 16192 KB Output is correct
36 Correct 521 ms 16444 KB Output is correct
37 Correct 746 ms 15140 KB Output is correct
38 Correct 857 ms 18060 KB Output is correct
39 Correct 953 ms 17476 KB Output is correct
40 Correct 894 ms 18948 KB Output is correct
41 Correct 903 ms 21556 KB Output is correct