oj.uz

답안 #535267

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535267 2022-03-09T20:52:00 Z LucaDantas 007 (CEOI14_007) C++17
0 / 100
 305 ms 27876 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 2e5+10;

vector<int> g[maxn];

int dist[2][maxn];

void bfs(int k, int s) {
	dist[k][s] = 0;
	queue<int> q;
	q.push(s);

	while(q.size()) {
		int u = q.front(); q.pop();

		for(int v : g[u])
			if(dist[k][v] > dist[k][u]+1)
				dist[k][v] = dist[k][u]+1, q.push(v);
	}
}

bool mark[maxn];

void dfs(int u, int& mn) {
	mark[u] = 1;
	mn = min(mn, dist[0][u]);
	for(int v : g[u])
		if(!mark[v] && dist[0][v] == dist[1][v]) dfs(v, mn);
}

int main() {
	int n, m; scanf("%d %d", &n, &m);
	int s, t, a, b; scanf("%d %d %d %d", &s, &t, &a, &b);

	for(int i = 0; i < m; i++) {
		int u, v; scanf("%d %d", &u, &v);
		g[u].push_back(v); g[v].push_back(u);
	}
	
	memset(dist, 0x3f, sizeof dist); // já coloco infinito pra todo mundo
	bfs(0, a);
	bfs(1, b);

	int especial = 0;
	if(dist[0][s] == dist[1][s] && dist[0][t] == dist[1][t]) {
		memset(mark, 0, sizeof mark);
		int S = 0x3f3f3f3f; dfs(s, S);

		memset(mark, 0, sizeof mark);
		int T = 0x3f3f3f3f; dfs(t, T);

		if(S > T) especial = 1;
	}

	printf("%d\n", max(-1, min(dist[0][t] - dist[0][s], dist[1][t] - dist[1][s]) - especial));
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:34:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  int n, m; scanf("%d %d", &n, &m);
      |            ~~~~~^~~~~~~~~~~~~~~~~
007.cpp:35:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  int s, t, a, b; scanf("%d %d %d %d", &s, &t, &a, &b);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:38:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   int u, v; scanf("%d %d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 30.0

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

Subtask #2
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 8520 KB Output is correct
2 Correct 30 ms 9512 KB Output is correct
3 Correct 30 ms 8572 KB Output is correct
4 Correct 35 ms 9524 KB Output is correct
5 Correct 32 ms 8224 KB Output is correct
6 Correct 29 ms 8396 KB Output is correct
7 Correct 29 ms 8736 KB Output is correct
8 Correct 28 ms 8868 KB Output is correct
9 Incorrect 39 ms 10696 KB Output isn't correct
10 Correct 153 ms 19464 KB Output is correct
11 Incorrect 64 ms 10976 KB Output isn't correct
12 Correct 77 ms 11724 KB Output is correct
13 Correct 56 ms 10928 KB Output is correct
14 Correct 43 ms 10224 KB Output is correct
15 Correct 64 ms 11828 KB Output is correct
16 Correct 90 ms 11852 KB Output is correct
17 Correct 82 ms 11376 KB Output is correct
18 Correct 61 ms 11404 KB Output is correct
19 Correct 112 ms 16380 KB Output is correct
20 Incorrect 237 ms 22388 KB Output isn't correct
21 Correct 111 ms 14236 KB Output is correct
22 Correct 71 ms 12808 KB Output is correct
23 Correct 95 ms 13440 KB Output is correct
24 Correct 99 ms 13776 KB Output is correct
25 Incorrect 87 ms 13216 KB Output isn't correct
26 Correct 113 ms 12692 KB Output is correct
27 Correct 131 ms 13748 KB Output is correct
28 Correct 101 ms 13708 KB Output is correct
29 Correct 159 ms 19000 KB Output is correct
30 Incorrect 232 ms 23376 KB Output isn't correct
31 Correct 94 ms 15284 KB Output is correct
32 Correct 96 ms 13800 KB Output is correct
33 Correct 111 ms 13684 KB Output is correct
34 Incorrect 125 ms 14468 KB Output isn't correct
35 Correct 81 ms 14524 KB Output is correct
36 Correct 96 ms 15236 KB Output is correct
37 Correct 128 ms 15028 KB Output is correct
38 Correct 141 ms 15092 KB Output is correct
39 Correct 116 ms 15076 KB Output is correct
40 Correct 186 ms 22928 KB Output is correct
41 Correct 305 ms 27876 KB Output is correct