Submission #392387

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
392387	2021-04-21T01:16:19 Z	8e7	007 (CEOI14_007)	C++14	100 / 100	305 ms	17820 KB

007

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);
using namespace std;
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
//template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_upate>;

vector<int> adj[maxn];
int d1[maxn], d2[maxn], d3[maxn], d4[maxn];
bool found[maxn];

void bfs(int n, int s, int dep[]) {
	for (int i = 1;i <= n;i++) found[i] = false;
	queue<int> que;
	que.push(s);
	dep[s] = 0;
	while (que.size()) {
		int cur = que.front();
		que.pop();
		found[cur] = 1;
		for (int v:adj[cur]) {
			if (!found[v]) {
				found[v] = 1;
				dep[v] = dep[cur] + 1;
				que.push(v);
			}
		}
	}
}
int main() {
	io
	int n, m;
	cin >> n >> m;
	int pa, pb, st, st2;
	cin >> pa >> pb >> st >> st2;
	for (int i = 0;i < m;i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	bfs(n, st, d1);
	bfs(n, st2, d2);
	bfs(n, pa, d3);
	bfs(n, pb, d4);

	if (d1[pa] == d2[pa] && d1[pb] == d2[pb]) {
		int ans = d1[pb] - d1[pa];
		int ma = 1<<30, mb = 1<<30;
		for (int i = 1;i <= n;i++) {
			if (d3[i] + d1[i] == d1[pa] && d1[i] == d2[i]) { //if on shortest path
				ma = min(ma, d1[i]);
			}
			if (d4[i] + d1[i] == d1[pb] && d1[i] == d2[i]) {
				mb = min(mb, d1[i]);
			}
		}
		if (ma > mb) ans--;
		cout << (ans >= 0 ? ans : -1) << "\n";
	} else {
		int ans = min(d1[pb] - d1[pa], d2[pb] - d2[pa]);
		cout << (ans >= 0 ? ans : -1) << "\n";
	}
}
/*
6 6
1 2 3 4
1 5
5 6
6 3
6 4
1 2
3 4

7 8
1 7 4 5
4 5
1 2
1 3
2 4
3 5
4 6
5 6
6 7


 */

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4940 KB	Output is correct
2	Correct	3 ms	4940 KB	Output is correct
3	Correct	3 ms	4940 KB	Output is correct
4	Correct	3 ms	5004 KB	Output is correct
5	Correct	3 ms	4940 KB	Output is correct
6	Correct	3 ms	4940 KB	Output is correct
7	Correct	3 ms	4940 KB	Output is correct
8	Correct	3 ms	4940 KB	Output is correct
9	Correct	4 ms	5124 KB	Output is correct
10	Correct	3 ms	4940 KB	Output is correct
11	Correct	4 ms	5048 KB	Output is correct
12	Correct	3 ms	4940 KB	Output is correct
13	Correct	4 ms	5068 KB	Output is correct
14	Correct	3 ms	4940 KB	Output is correct
15	Correct	3 ms	4940 KB	Output is correct
16	Correct	3 ms	4940 KB	Output is correct
17	Correct	3 ms	5068 KB	Output is correct
18	Correct	3 ms	5068 KB	Output is correct
19	Correct	3 ms	5068 KB	Output is correct
20	Correct	3 ms	5068 KB	Output is correct
21	Correct	4 ms	5068 KB	Output is correct
22	Correct	4 ms	5064 KB	Output is correct
23	Correct	4 ms	5068 KB	Output is correct
24	Correct	4 ms	5008 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	6932 KB	Output is correct
2	Correct	34 ms	7804 KB	Output is correct
3	Correct	27 ms	7012 KB	Output is correct
4	Correct	34 ms	7952 KB	Output is correct
5	Correct	25 ms	6876 KB	Output is correct
6	Correct	25 ms	7160 KB	Output is correct
7	Correct	29 ms	7256 KB	Output is correct
8	Correct	31 ms	7284 KB	Output is correct
9	Correct	41 ms	7752 KB	Output is correct
10	Correct	146 ms	12176 KB	Output is correct
11	Correct	67 ms	9272 KB	Output is correct
12	Correct	103 ms	10336 KB	Output is correct
13	Correct	63 ms	9668 KB	Output is correct
14	Correct	49 ms	8948 KB	Output is correct
15	Correct	76 ms	10576 KB	Output is correct
16	Correct	94 ms	10820 KB	Output is correct
17	Correct	75 ms	10248 KB	Output is correct
18	Correct	77 ms	10184 KB	Output is correct
19	Correct	110 ms	11460 KB	Output is correct
20	Correct	216 ms	14296 KB	Output is correct
21	Correct	110 ms	12744 KB	Output is correct
22	Correct	109 ms	11672 KB	Output is correct
23	Correct	111 ms	12508 KB	Output is correct
24	Correct	107 ms	12608 KB	Output is correct
25	Correct	107 ms	12148 KB	Output is correct
26	Correct	96 ms	11700 KB	Output is correct
27	Correct	119 ms	12656 KB	Output is correct
28	Correct	132 ms	12592 KB	Output is correct
29	Correct	151 ms	13116 KB	Output is correct
30	Correct	208 ms	15088 KB	Output is correct
31	Correct	134 ms	13768 KB	Output is correct
32	Correct	128 ms	12608 KB	Output is correct
33	Correct	132 ms	12992 KB	Output is correct
34	Correct	152 ms	13228 KB	Output is correct
35	Correct	115 ms	12868 KB	Output is correct
36	Correct	117 ms	13252 KB	Output is correct
37	Correct	152 ms	14404 KB	Output is correct
38	Correct	161 ms	14076 KB	Output is correct
39	Correct	180 ms	14116 KB	Output is correct
40	Correct	201 ms	15660 KB	Output is correct
41	Correct	305 ms	17820 KB	Output is correct