Submission #551673

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
551673	2022-04-21T09:56:46 Z	AugustinasJucas	007 (CEOI14_007)	C++14	30 / 100	811 ms	18728 KB

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.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;
		}
	}
	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.0 / 30.0

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

Subtask #2

21.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	61 ms	7088 KB	Partially correct
2	Correct	78 ms	8044 KB	Output is correct
3	Partially correct	68 ms	7188 KB	Partially correct
4	Correct	132 ms	8140 KB	Output is correct
5	Partially correct	61 ms	7028 KB	Partially correct
6	Partially correct	66 ms	7248 KB	Partially correct
7	Partially correct	79 ms	7548 KB	Partially correct
8	Partially correct	85 ms	7512 KB	Partially correct
9	Correct	93 ms	7968 KB	Output is correct
10	Partially correct	291 ms	12408 KB	Partially correct
11	Correct	162 ms	9644 KB	Output is correct
12	Partially correct	298 ms	10800 KB	Partially correct
13	Correct	265 ms	10016 KB	Output is correct
14	Correct	150 ms	9232 KB	Output is correct
15	Partially correct	365 ms	10952 KB	Partially correct
16	Partially correct	322 ms	11264 KB	Partially correct
17	Partially correct	275 ms	10604 KB	Partially correct
18	Correct	350 ms	10592 KB	Output is correct
19	Partially correct	374 ms	11800 KB	Partially correct
20	Correct	533 ms	14788 KB	Output is correct
21	Correct	567 ms	13256 KB	Output is correct
22	Partially correct	493 ms	12268 KB	Partially correct
23	Partially correct	579 ms	13084 KB	Partially correct
24	Partially correct	573 ms	13000 KB	Partially correct
25	Correct	400 ms	12660 KB	Output is correct
26	Partially correct	426 ms	12196 KB	Partially correct
27	Partially correct	446 ms	13208 KB	Partially correct
28	Partially correct	561 ms	13156 KB	Partially correct
29	Partially correct	552 ms	13568 KB	Partially correct
30	Correct	488 ms	15500 KB	Output is correct
31	Correct	583 ms	14392 KB	Output is correct
32	Partially correct	565 ms	13176 KB	Partially correct
33	Partially correct	483 ms	13416 KB	Partially correct
34	Correct	724 ms	13888 KB	Output is correct
35	Correct	572 ms	13476 KB	Output is correct
36	Correct	594 ms	13756 KB	Output is correct
37	Partially correct	790 ms	14956 KB	Partially correct
38	Partially correct	755 ms	14720 KB	Partially correct
39	Partially correct	811 ms	14716 KB	Partially correct
40	Correct	677 ms	16236 KB	Output is correct
41	Partially correct	806 ms	18728 KB	Partially correct