답안 #101173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
101173	2019-03-17T08:05:23 Z	square1001	007 (CEOI14_007)	C++14	30 / 100	330 ms	16512 KB

007

#include <queue>
#include <vector>
#include <iostream>
using namespace std;
vector<int> shortest_path(int src, vector<vector<int> > &G) {
	int N = G.size();
	vector<int> dist(N, -1);
	queue<int> que;
	que.push(src);
	dist[src] = 0;
	while (!que.empty()) {
		int u = que.front(); que.pop();
		for (int i : G[u]) {
			if (dist[i] == -1) {
				dist[i] = dist[u] + 1;
				que.push(i);
			}
		}
	}
	return dist;
}
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	int S, D, A, B;
	cin >> S >> D >> A >> B; --S, --D, --A, --B;
	vector<vector<int> > G(N);
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b; --a, --b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	vector<int> da = shortest_path(A, G);
	vector<int> db = shortest_path(B, G);
	int s1 = min(da[D] - da[S], db[D] - da[S] - 1);
	int s2 = min(db[D] - db[S], da[D] - db[S] - 1);
	int ans = max(s1, s2);
	if (ans < 0) cout << -1 << endl;
	else cout << ans << endl;
	return 0;
}

Subtask #1

9.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Partially correct	2 ms	384 KB	Partially correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Partially correct	3 ms	384 KB	Partially correct
7	Partially correct	2 ms	384 KB	Partially correct
8	Correct	3 ms	384 KB	Output is correct
9	Partially correct	2 ms	384 KB	Partially correct
10	Correct	2 ms	256 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	304 KB	Output is correct
13	Partially correct	2 ms	384 KB	Partially correct
14	Correct	3 ms	384 KB	Output is correct
15	Partially correct	3 ms	256 KB	Partially correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	3 ms	356 KB	Output is correct
18	Correct	3 ms	384 KB	Output is correct
19	Partially correct	4 ms	384 KB	Partially correct
20	Partially correct	4 ms	512 KB	Partially correct
21	Correct	2 ms	384 KB	Output is correct
22	Partially correct	2 ms	384 KB	Partially correct
23	Partially correct	2 ms	384 KB	Partially correct
24	Correct	3 ms	384 KB	Output is correct

Subtask #2

21.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	23 ms	3448 KB	Partially correct
2	Correct	46 ms	4664 KB	Output is correct
3	Partially correct	27 ms	3580 KB	Partially correct
4	Correct	46 ms	4984 KB	Output is correct
5	Correct	25 ms	3328 KB	Output is correct
6	Correct	29 ms	3712 KB	Output is correct
7	Partially correct	29 ms	3968 KB	Partially correct
8	Partially correct	28 ms	3960 KB	Partially correct
9	Correct	47 ms	4472 KB	Output is correct
10	Partially correct	187 ms	9080 KB	Partially correct
11	Correct	59 ms	6648 KB	Output is correct
12	Partially correct	80 ms	8324 KB	Partially correct
13	Correct	97 ms	7288 KB	Output is correct
14	Correct	56 ms	6188 KB	Output is correct
15	Partially correct	96 ms	8312 KB	Partially correct
16	Correct	90 ms	8696 KB	Output is correct
17	Partially correct	83 ms	7928 KB	Partially correct
18	Correct	91 ms	7900 KB	Output is correct
19	Partially correct	131 ms	9064 KB	Partially correct
20	Correct	279 ms	12024 KB	Output is correct
21	Correct	107 ms	11128 KB	Output is correct
22	Partially correct	124 ms	9952 KB	Partially correct
23	Correct	132 ms	10912 KB	Output is correct
24	Partially correct	139 ms	10872 KB	Partially correct
25	Correct	164 ms	10400 KB	Output is correct
26	Correct	119 ms	9848 KB	Output is correct
27	Partially correct	125 ms	11128 KB	Partially correct
28	Partially correct	136 ms	11064 KB	Partially correct
29	Partially correct	178 ms	11256 KB	Partially correct
30	Correct	257 ms	12928 KB	Output is correct
31	Correct	154 ms	12656 KB	Output is correct
32	Partially correct	139 ms	10872 KB	Partially correct
33	Correct	140 ms	11428 KB	Output is correct
34	Correct	191 ms	11908 KB	Output is correct
35	Correct	129 ms	11388 KB	Output is correct
36	Correct	145 ms	12024 KB	Output is correct
37	Correct	204 ms	13304 KB	Output is correct
38	Partially correct	163 ms	12920 KB	Partially correct
39	Partially correct	216 ms	13120 KB	Partially correct
40	Correct	230 ms	14328 KB	Output is correct
41	Partially correct	330 ms	16512 KB	Partially correct