답안 #391893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391893	2021-04-20T05:15:23 Z	8e7	007 (CEOI14_007)	C++14	0 / 100	257 ms	16896 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);
	}
	int d1 = 0, d2 = 0;
	bfs(st);
	d1 = dep[pb] - dep[pa];
	int ans = dep[pb] - dep[pa];

	for (int i = 1;i <= n;i++) found[i] = 0;
	bfs(st2);
	d2 = dep[pb] - dep[pa];
	ans = min(d1, d2);
	//ans = min(ans, dep[pb] - dep[pa]);

	if (d1 != d2) cout << (ans > 0 ? ans - 1 : -1) << "\n";
	else cout << (ans > 0 ? ans : -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

0.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	4 ms	4940 KB	Partially correct
2	Correct	3 ms	4940 KB	Output is correct
3	Partially correct	3 ms	4940 KB	Partially correct
4	Incorrect	3 ms	4940 KB	Output isn't correct
5	Incorrect	3 ms	4940 KB	Output isn't correct
6	Correct	4 ms	4940 KB	Output is correct
7	Correct	4 ms	4940 KB	Output is correct
8	Incorrect	4 ms	4924 KB	Output isn't correct
9	Correct	4 ms	4940 KB	Output is correct
10	Partially correct	4 ms	4940 KB	Partially correct
11	Partially correct	3 ms	4940 KB	Partially correct
12	Incorrect	4 ms	4940 KB	Output isn't correct
13	Correct	4 ms	4940 KB	Output is correct
14	Incorrect	3 ms	4940 KB	Output isn't correct
15	Correct	3 ms	4940 KB	Output is correct
16	Incorrect	3 ms	4940 KB	Output isn't correct
17	Incorrect	4 ms	4940 KB	Output isn't correct
18	Incorrect	3 ms	4940 KB	Output isn't correct
19	Correct	5 ms	4940 KB	Output is correct
20	Correct	4 ms	4940 KB	Output is correct
21	Partially correct	4 ms	4940 KB	Partially correct
22	Correct	4 ms	4940 KB	Output is correct
23	Correct	4 ms	4940 KB	Output is correct
24	Incorrect	4 ms	5068 KB	Output isn't correct

Subtask #2

0.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	6980 KB	Output is correct
2	Incorrect	31 ms	7732 KB	Output isn't correct
3	Correct	25 ms	7040 KB	Output is correct
4	Incorrect	30 ms	7808 KB	Output isn't correct
5	Partially correct	22 ms	6860 KB	Partially correct
6	Partially correct	22 ms	7068 KB	Partially correct
7	Correct	25 ms	7356 KB	Output is correct
8	Correct	25 ms	7348 KB	Output is correct
9	Incorrect	38 ms	8092 KB	Output isn't correct
10	Correct	144 ms	12472 KB	Output is correct
11	Incorrect	49 ms	9316 KB	Output isn't correct
12	Correct	64 ms	10180 KB	Output is correct
13	Incorrect	54 ms	9612 KB	Output isn't correct
14	Correct	43 ms	8872 KB	Output is correct
15	Correct	64 ms	10168 KB	Output is correct
16	Partially correct	64 ms	10440 KB	Partially correct
17	Correct	60 ms	10028 KB	Output is correct
18	Incorrect	69 ms	9984 KB	Output isn't correct
19	Correct	102 ms	11156 KB	Output is correct
20	Incorrect	172 ms	13972 KB	Output isn't correct
21	Incorrect	93 ms	11868 KB	Output isn't correct
22	Correct	77 ms	11016 KB	Output is correct
23	Correct	96 ms	11716 KB	Output is correct
24	Correct	90 ms	11748 KB	Output is correct
25	Incorrect	88 ms	11460 KB	Output isn't correct
26	Correct	80 ms	11072 KB	Output is correct
27	Correct	93 ms	11796 KB	Output is correct
28	Correct	111 ms	11860 KB	Output is correct
29	Correct	125 ms	12536 KB	Output is correct
30	Incorrect	223 ms	14600 KB	Output isn't correct
31	Incorrect	120 ms	12760 KB	Output isn't correct
32	Correct	131 ms	11904 KB	Output is correct
33	Correct	106 ms	11972 KB	Output is correct
34	Incorrect	114 ms	12308 KB	Output isn't correct
35	Incorrect	107 ms	11972 KB	Output isn't correct
36	Incorrect	113 ms	12336 KB	Output isn't correct
37	Partially correct	120 ms	13064 KB	Partially correct
38	Correct	126 ms	12908 KB	Output is correct
39	Correct	146 ms	12972 KB	Output is correct
40	Incorrect	176 ms	14800 KB	Output isn't correct
41	Correct	257 ms	16896 KB	Output is correct