oj.uz

Submission #535269

# Submission time Handle Problem Language Result Execution time Memory
535269 2022-03-09T20:52:43 Z LucaDantas 007 (CEOI14_007) C++17
30 / 100
 227 ms 16324 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[1][t]) - min(dist[0][s], dist[1][s]) - 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
9.0 / 30.0

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

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 22 ms 7760 KB Partially correct
2 Correct 32 ms 8400 KB Output is correct
3 Partially correct 25 ms 7872 KB Partially correct
4 Correct 29 ms 8396 KB Output is correct
5 Correct 20 ms 7764 KB Output is correct
6 Correct 24 ms 7920 KB Output is correct
7 Partially correct 25 ms 8020 KB Partially correct
8 Partially correct 24 ms 8032 KB Partially correct
9 Correct 46 ms 8436 KB Output is correct
10 Partially correct 139 ms 12620 KB Partially correct
11 Correct 48 ms 9376 KB Output is correct
12 Partially correct 65 ms 10004 KB Partially correct
13 Correct 51 ms 9692 KB Output is correct
14 Correct 49 ms 9072 KB Output is correct
15 Partially correct 68 ms 10140 KB Partially correct
16 Correct 78 ms 10380 KB Output is correct
17 Partially correct 60 ms 9964 KB Partially correct
18 Correct 50 ms 9972 KB Output is correct
19 Partially correct 83 ms 11080 KB Partially correct
20 Correct 175 ms 13872 KB Output is correct
21 Correct 94 ms 11480 KB Output is correct
22 Partially correct 78 ms 10852 KB Partially correct
23 Partially correct 75 ms 11504 KB Partially correct
24 Partially correct 94 ms 11416 KB Partially correct
25 Correct 84 ms 11200 KB Output is correct
26 Partially correct 86 ms 10864 KB Partially correct
27 Partially correct 83 ms 11692 KB Partially correct
28 Partially correct 110 ms 11576 KB Partially correct
29 Partially correct 131 ms 12252 KB Partially correct
30 Correct 206 ms 14412 KB Output is correct
31 Correct 110 ms 12280 KB Output is correct
32 Partially correct 101 ms 11440 KB Partially correct
33 Partially correct 97 ms 11588 KB Partially correct
34 Correct 99 ms 11852 KB Output is correct
35 Correct 102 ms 11720 KB Output is correct
36 Correct 100 ms 11920 KB Output is correct
37 Correct 119 ms 12620 KB Output is correct
38 Partially correct 107 ms 12408 KB Partially correct
39 Partially correct 131 ms 12520 KB Partially correct
40 Correct 171 ms 14148 KB Output is correct
41 Partially correct 227 ms 16324 KB Partially correct