oj.uz

Submission #535255

# Submission time Handle Problem Language Result Execution time Memory
535255 2022-03-09T19:52:40 Z LucaDantas 007 (CEOI14_007) C++17
0 / 100
 139 ms 13184 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);

	// s -> 007, t -> malvado
	if(t == a || t == b) return puts("-1"), 0;

	for(int i = 0; i < n; 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]) {
		int S = 0; dfs(s, S);
		memset(mark, 0, sizeof mark);
		int T = 0; dfs(t, T);
		memset(mark, 0, sizeof mark);

		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:41:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   int u, v; scanf("%d %d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6476 KB Output is correct
2 Correct 4 ms 6476 KB Output is correct
3 Correct 5 ms 6732 KB Output is correct
4 Incorrect 3 ms 6732 KB Output isn't correct
5 Incorrect 4 ms 6732 KB Output isn't correct
6 Incorrect 3 ms 6732 KB Output isn't correct
7 Incorrect 4 ms 6732 KB Output isn't correct
8 Correct 3 ms 6740 KB Output is correct
9 Correct 4 ms 6732 KB Output is correct
10 Correct 3 ms 6476 KB Output is correct
11 Correct 3 ms 6476 KB Output is correct
12 Incorrect 3 ms 6732 KB Output isn't correct
13 Correct 3 ms 6732 KB Output is correct
14 Incorrect 4 ms 6476 KB Output isn't correct
15 Incorrect 3 ms 6732 KB Output isn't correct
16 Incorrect 3 ms 6732 KB Output isn't correct
17 Incorrect 3 ms 6732 KB Output isn't correct
18 Incorrect 4 ms 6732 KB Output isn't correct
19 Correct 4 ms 6732 KB Output is correct
20 Correct 3 ms 6732 KB Output is correct
21 Correct 3 ms 6476 KB Output is correct
22 Incorrect 4 ms 6476 KB Output isn't correct
23 Correct 3 ms 6476 KB Output is correct
24 Correct 3 ms 6732 KB Output is correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 7972 KB Output is correct
2 Incorrect 37 ms 8800 KB Output isn't correct
3 Correct 20 ms 8012 KB Output is correct
4 Incorrect 26 ms 8728 KB Output isn't correct
5 Correct 21 ms 7628 KB Output is correct
6 Correct 23 ms 7960 KB Output is correct
7 Incorrect 22 ms 8012 KB Output isn't correct
8 Incorrect 25 ms 8072 KB Output isn't correct
9 Incorrect 19 ms 8256 KB Output isn't correct
10 Incorrect 23 ms 8652 KB Output isn't correct
11 Incorrect 55 ms 9780 KB Output isn't correct
12 Correct 64 ms 9952 KB Output is correct
13 Incorrect 59 ms 9500 KB Output isn't correct
14 Correct 36 ms 9196 KB Output is correct
15 Correct 68 ms 10364 KB Output is correct
16 Correct 72 ms 10364 KB Output is correct
17 Incorrect 55 ms 9936 KB Output isn't correct
18 Incorrect 70 ms 9856 KB Output isn't correct
19 Incorrect 40 ms 10184 KB Output isn't correct
20 Incorrect 41 ms 10344 KB Output isn't correct
21 Incorrect 77 ms 12176 KB Output isn't correct
22 Correct 90 ms 11160 KB Output is correct
23 Correct 102 ms 11496 KB Output is correct
24 Correct 73 ms 11928 KB Output is correct
25 Incorrect 71 ms 11348 KB Output isn't correct
26 Correct 75 ms 10912 KB Output is correct
27 Incorrect 97 ms 11496 KB Output isn't correct
28 Incorrect 125 ms 11412 KB Output isn't correct
29 Incorrect 52 ms 11024 KB Output isn't correct
30 Incorrect 47 ms 10820 KB Output isn't correct
31 Incorrect 95 ms 13184 KB Output isn't correct
32 Correct 80 ms 11428 KB Output is correct
33 Correct 103 ms 11656 KB Output is correct
34 Incorrect 116 ms 11844 KB Output isn't correct
35 Incorrect 81 ms 12360 KB Output isn't correct
36 Incorrect 95 ms 13016 KB Output isn't correct
37 Correct 139 ms 12608 KB Output is correct
38 Incorrect 134 ms 12536 KB Output isn't correct
39 Correct 104 ms 12356 KB Output is correct
40 Incorrect 66 ms 12368 KB Output isn't correct
41 Incorrect 69 ms 12400 KB Output isn't correct