oj.uz

Submission #535271

# Submission time Handle Problem Language Result Execution time Memory
535271 2022-03-09T20:56:35 Z LucaDantas 007 (CEOI14_007) C++17
0 / 100
 256 ms 33036 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]) {
		assert(0);
		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
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 5 ms 6484 KB Output is correct
3 Runtime error 12 ms 13140 KB Execution killed with signal 6
4 Runtime error 9 ms 13140 KB Execution killed with signal 6
5 Runtime error 8 ms 13140 KB Execution killed with signal 6
6 Runtime error 8 ms 13060 KB Execution killed with signal 6
7 Runtime error 8 ms 13140 KB Execution killed with signal 6
8 Runtime error 8 ms 13140 KB Execution killed with signal 6
9 Runtime error 8 ms 13140 KB Execution killed with signal 6
10 Correct 3 ms 6484 KB Output is correct
11 Correct 3 ms 6484 KB Output is correct
12 Runtime error 8 ms 13104 KB Execution killed with signal 6
13 Runtime error 8 ms 13140 KB Execution killed with signal 6
14 Runtime error 8 ms 13140 KB Execution killed with signal 6
15 Runtime error 8 ms 13140 KB Execution killed with signal 6
16 Runtime error 9 ms 13120 KB Execution killed with signal 6
17 Runtime error 9 ms 13140 KB Execution killed with signal 6
18 Runtime error 8 ms 13140 KB Execution killed with signal 6
19 Runtime error 9 ms 13140 KB Execution killed with signal 6
20 Runtime error 12 ms 13140 KB Execution killed with signal 6
21 Correct 5 ms 6536 KB Output is correct
22 Runtime error 11 ms 13096 KB Execution killed with signal 6
23 Runtime error 12 ms 13152 KB Execution killed with signal 6
24 Runtime error 9 ms 13140 KB Execution killed with signal 6

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 15740 KB Execution killed with signal 6
2 Runtime error 30 ms 16828 KB Execution killed with signal 6
3 Runtime error 26 ms 15852 KB Execution killed with signal 6
4 Runtime error 30 ms 16964 KB Execution killed with signal 6
5 Correct 20 ms 7764 KB Output is correct
6 Correct 24 ms 7972 KB Output is correct
7 Runtime error 41 ms 16244 KB Execution killed with signal 6
8 Runtime error 34 ms 16212 KB Execution killed with signal 6
9 Runtime error 45 ms 17032 KB Execution killed with signal 6
10 Runtime error 128 ms 25644 KB Execution killed with signal 6
11 Runtime error 46 ms 18864 KB Execution killed with signal 6
12 Runtime error 76 ms 20296 KB Execution killed with signal 6
13 Runtime error 71 ms 19324 KB Execution killed with signal 6
14 Runtime error 55 ms 18336 KB Execution killed with signal 6
15 Runtime error 73 ms 20384 KB Execution killed with signal 6
16 Correct 56 ms 10372 KB Output is correct
17 Runtime error 53 ms 20020 KB Execution killed with signal 6
18 Runtime error 56 ms 19992 KB Execution killed with signal 6
19 Runtime error 89 ms 22364 KB Execution killed with signal 6
20 Runtime error 196 ms 28096 KB Execution killed with signal 6
21 Runtime error 103 ms 23292 KB Execution killed with signal 6
22 Runtime error 70 ms 21880 KB Execution killed with signal 6
23 Correct 83 ms 11452 KB Output is correct
24 Runtime error 87 ms 23024 KB Execution killed with signal 6
25 Runtime error 109 ms 22464 KB Execution killed with signal 6
26 Correct 88 ms 10904 KB Output is correct
27 Runtime error 101 ms 23220 KB Execution killed with signal 6
28 Runtime error 106 ms 23312 KB Execution killed with signal 6
29 Runtime error 134 ms 24896 KB Execution killed with signal 6
30 Runtime error 213 ms 29064 KB Execution killed with signal 6
31 Runtime error 111 ms 24780 KB Execution killed with signal 6
32 Runtime error 105 ms 23156 KB Execution killed with signal 6
33 Correct 104 ms 11664 KB Output is correct
34 Runtime error 123 ms 24128 KB Execution killed with signal 6
35 Runtime error 98 ms 23560 KB Execution killed with signal 6
36 Runtime error 84 ms 23984 KB Execution killed with signal 6
37 Correct 114 ms 12620 KB Output is correct
38 Runtime error 129 ms 25188 KB Execution killed with signal 6
39 Runtime error 126 ms 25284 KB Execution killed with signal 6
40 Runtime error 154 ms 28488 KB Execution killed with signal 6
41 Runtime error 256 ms 33036 KB Execution killed with signal 6