oj.uz

답안 #391894

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391894 2021-04-20T05:15:54 Z 8e7 007 (CEOI14_007) C++14
30 / 100
 260 ms 15684 KB 
//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) << "\n";
	else 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

# 결과 실행 시간 메모리 Grader output
1 Partially correct 3 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 4940 KB Output is correct
6 Partially correct 3 ms 4940 KB Partially correct
7 Partially correct 3 ms 4996 KB Partially correct
8 Correct 3 ms 4940 KB Output is correct
9 Partially correct 3 ms 4940 KB Partially correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Partially correct 4 ms 4940 KB Partially correct
14 Correct 3 ms 4940 KB Output is correct
15 Partially correct 3 ms 4940 KB Partially correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 4 ms 5068 KB Output is correct
18 Correct 3 ms 4940 KB Output is correct
19 Partially correct 4 ms 4940 KB Partially correct
20 Partially correct 3 ms 4940 KB Partially correct
21 Correct 4 ms 5040 KB Output is correct
22 Partially correct 4 ms 4940 KB Partially correct
23 Partially correct 3 ms 4940 KB Partially correct
24 Correct 4 ms 4944 KB Output is correct

Subtask #2
21.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 21 ms 6504 KB Partially correct
2 Correct 32 ms 7148 KB Output is correct
3 Partially correct 24 ms 6476 KB Partially correct
4 Correct 33 ms 7108 KB Output is correct
5 Correct 21 ms 6308 KB Output is correct
6 Correct 22 ms 6588 KB Output is correct
7 Partially correct 26 ms 6808 KB Partially correct
8 Partially correct 29 ms 6912 KB Partially correct
9 Correct 37 ms 7208 KB Output is correct
10 Partially correct 138 ms 11528 KB Partially correct
11 Correct 45 ms 8268 KB Output is correct
12 Partially correct 75 ms 9080 KB Partially correct
13 Correct 55 ms 8516 KB Output is correct
14 Correct 44 ms 7980 KB Output is correct
15 Partially correct 63 ms 9156 KB Partially correct
16 Correct 79 ms 9416 KB Output is correct
17 Partially correct 56 ms 8952 KB Partially correct
18 Correct 59 ms 8896 KB Output is correct
19 Partially correct 96 ms 10144 KB Partially correct
20 Correct 181 ms 12844 KB Output is correct
21 Correct 87 ms 10832 KB Output is correct
22 Partially correct 103 ms 10028 KB Partially correct
23 Partially correct 100 ms 10676 KB Partially correct
24 Partially correct 103 ms 10672 KB Partially correct
25 Correct 92 ms 10364 KB Output is correct
26 Partially correct 83 ms 10108 KB Partially correct
27 Partially correct 110 ms 10692 KB Partially correct
28 Partially correct 106 ms 10692 KB Partially correct
29 Partially correct 126 ms 11380 KB Partially correct
30 Correct 194 ms 13488 KB Output is correct
31 Correct 125 ms 11588 KB Output is correct
32 Partially correct 104 ms 10740 KB Partially correct
33 Partially correct 111 ms 10936 KB Partially correct
34 Correct 117 ms 11144 KB Output is correct
35 Correct 117 ms 11108 KB Output is correct
36 Correct 100 ms 11112 KB Output is correct
37 Correct 128 ms 12044 KB Output is correct
38 Partially correct 131 ms 11808 KB Partially correct
39 Partially correct 149 ms 11832 KB Partially correct
40 Correct 170 ms 13428 KB Output is correct
41 Partially correct 260 ms 15684 KB Partially correct