Submission #391857

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
391857	2021-04-20T03:59:18 Z	8e7	007 (CEOI14_007)	C++14	30 / 100	268 ms	15688 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 dep[maxn];
bool found[maxn];

void bfs(int s) {
	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(st);
	//cout << dep[pb] << " " << dep[pa] << endl;
	int ans = dep[pb] - dep[pa];

	for (int i = 1;i <= n;i++) found[i] = 0;
	bfs(st2);
	//cout << dep[pb] << " " << dep[pa] << endl;
	ans = min(ans, dep[pb] - dep[pa]);
	cout << (ans > 0 ? ans - 1 : -1) << "\n";
}
/*
6 6
1 2 3 4
1 5
5 6
6 3
6 4
1 2
3 4

3 3
3 1 1 2
1 2
2 3
3 1
 */

Subtask #1

9.0 / 30.0

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

Subtask #2

21.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	24 ms	6468 KB	Partially correct
2	Correct	38 ms	7108 KB	Output is correct
3	Partially correct	23 ms	6476 KB	Partially correct
4	Correct	29 ms	7156 KB	Output is correct
5	Partially correct	25 ms	6408 KB	Partially correct
6	Partially correct	21 ms	6604 KB	Partially correct
7	Partially correct	24 ms	6804 KB	Partially correct
8	Partially correct	28 ms	6768 KB	Partially correct
9	Correct	35 ms	7096 KB	Output is correct
10	Partially correct	146 ms	11460 KB	Partially correct
11	Correct	62 ms	8256 KB	Output is correct
12	Partially correct	81 ms	9100 KB	Partially correct
13	Correct	67 ms	8540 KB	Output is correct
14	Correct	50 ms	7980 KB	Output is correct
15	Partially correct	91 ms	9180 KB	Partially correct
16	Partially correct	80 ms	9508 KB	Partially correct
17	Partially correct	57 ms	8904 KB	Partially correct
18	Correct	79 ms	8864 KB	Output is correct
19	Partially correct	103 ms	10120 KB	Partially correct
20	Correct	184 ms	12868 KB	Output is correct
21	Correct	108 ms	10808 KB	Output is correct
22	Partially correct	102 ms	9940 KB	Partially correct
23	Partially correct	113 ms	10692 KB	Partially correct
24	Partially correct	85 ms	10624 KB	Partially correct
25	Correct	89 ms	10388 KB	Output is correct
26	Partially correct	92 ms	10052 KB	Partially correct
27	Partially correct	92 ms	10904 KB	Partially correct
28	Partially correct	120 ms	10764 KB	Partially correct
29	Partially correct	152 ms	11460 KB	Partially correct
30	Correct	207 ms	13528 KB	Output is correct
31	Correct	131 ms	11588 KB	Output is correct
32	Partially correct	122 ms	10664 KB	Partially correct
33	Partially correct	112 ms	10948 KB	Partially correct
34	Correct	109 ms	11204 KB	Output is correct
35	Correct	108 ms	10892 KB	Output is correct
36	Correct	93 ms	11204 KB	Output is correct
37	Partially correct	144 ms	11972 KB	Partially correct
38	Partially correct	154 ms	11884 KB	Partially correct
39	Partially correct	139 ms	11952 KB	Partially correct
40	Correct	207 ms	13420 KB	Output is correct
41	Partially correct	268 ms	15688 KB	Partially correct