oj.uz

Submission #101140

# Submission time Handle Problem Language Result Execution time Memory
101140 2019-03-17T04:56:38 Z E869120 007 (CEOI14_007) C++14
0 / 100
 414 ms 21492 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#pragma warning (disable: 4996)

int N, M, p, q, a, b, dist1[1 << 18], dist2[1 << 18], dista[1 << 18], dist[1 << 18];
vector<int>X[1 << 18];

vector<int> dijkstra(int pos) {
	queue<int>Q;
	for (int i = 1; i <= N; i++) dist[i] = (1 << 30);
	dist[pos] = 0; Q.push(pos);

	while (!Q.empty()) {
		int pos = Q.front(); Q.pop();
		for (int i = 0; i < X[pos].size(); i++) {
			if (dist[X[pos][i]] > dist[pos] + 1) {
				dist[X[pos][i]] = dist[pos] + 1;
				Q.push(X[pos][i]);
			}
		}
	}

	vector<int>vec;
	for (int i = 1; i <= N; i++) vec.push_back(dist[i]);
	return vec;
}

int main() {
	scanf("%d%d", &N, &M);
	scanf("%d%d%d%d", &p, &q, &a, &b);
	for (int i = 1; i <= M; i++) {
		int v1, v2; scanf("%d%d", &v1, &v2);
		X[v1].push_back(v2);
		X[v2].push_back(v1);
	}
	vector<int> V1 = dijkstra(a); for (int i = 0; i < V1.size(); i++) dist1[i + 1] = V1[i];
	vector<int> V2 = dijkstra(b); for (int i = 0; i < V2.size(); i++) dist2[i + 1] = V2[i];
	vector<int> V3 = dijkstra(q); for (int i = 0; i < V3.size(); i++) dista[i + 1] = V3[i];

	int minx = (1 << 30);
	for (int i = 1; i <= N; i++) {
		if (dist1[i] < dist1[p] || dist2[i] < dist2[p]) minx = min(minx, dista[i]);
	}
	cout << minx - 1 << endl;
	return 0;
}

Compilation message

007.cpp:6:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
007.cpp: In function 'std::vector<int> dijkstra(int)':
007.cpp:18:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < X[pos].size(); i++) {
                   ~~^~~~~~~~~~~~~~~
007.cpp: In function 'int main()':
007.cpp:39:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  vector<int> V1 = dijkstra(a); for (int i = 0; i < V1.size(); i++) dist1[i + 1] = V1[i];
                                                ~~^~~~~~~~~~~
007.cpp:40:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  vector<int> V2 = dijkstra(b); for (int i = 0; i < V2.size(); i++) dist2[i + 1] = V2[i];
                                                ~~^~~~~~~~~~~
007.cpp:41:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  vector<int> V3 = dijkstra(q); for (int i = 0; i < V3.size(); i++) dista[i + 1] = V3[i];
                                                ~~^~~~~~~~~~~
007.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
007.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &p, &q, &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:35:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int v1, v2; scanf("%d%d", &v1, &v2);
               ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 30.0

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

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 9332 KB Output is correct
2 Incorrect 55 ms 10228 KB Output isn't correct
3 Correct 48 ms 9316 KB Output is correct
4 Incorrect 86 ms 10480 KB Output isn't correct
5 Correct 54 ms 9140 KB Output is correct
6 Correct 53 ms 9420 KB Output is correct
7 Correct 55 ms 9724 KB Output is correct
8 Correct 40 ms 9716 KB Output is correct
9 Incorrect 92 ms 10100 KB Output isn't correct
10 Correct 214 ms 14688 KB Output is correct
11 Incorrect 99 ms 12204 KB Output isn't correct
12 Correct 127 ms 13572 KB Output is correct
13 Incorrect 130 ms 12516 KB Output isn't correct
14 Correct 84 ms 11636 KB Output is correct
15 Correct 147 ms 13680 KB Output is correct
16 Correct 136 ms 14072 KB Output is correct
17 Correct 127 ms 13320 KB Output is correct
18 Incorrect 104 ms 13280 KB Output isn't correct
19 Correct 165 ms 14452 KB Output is correct
20 Incorrect 292 ms 17396 KB Output isn't correct
21 Incorrect 177 ms 16492 KB Output isn't correct
22 Correct 161 ms 15348 KB Output is correct
23 Correct 185 ms 16340 KB Output is correct
24 Correct 172 ms 16332 KB Output is correct
25 Incorrect 183 ms 15828 KB Output isn't correct
26 Correct 205 ms 15464 KB Output is correct
27 Correct 220 ms 16368 KB Output is correct
28 Correct 200 ms 16588 KB Output is correct
29 Correct 258 ms 16944 KB Output is correct
30 Incorrect 382 ms 18380 KB Output isn't correct
31 Incorrect 201 ms 17740 KB Output isn't correct
32 Correct 184 ms 16432 KB Output is correct
33 Correct 189 ms 16624 KB Output is correct
34 Incorrect 225 ms 17240 KB Output isn't correct
35 Incorrect 168 ms 16644 KB Output isn't correct
36 Incorrect 167 ms 17004 KB Output isn't correct
37 Correct 200 ms 18284 KB Output is correct
38 Correct 278 ms 18024 KB Output is correct
39 Correct 213 ms 18032 KB Output is correct
40 Incorrect 319 ms 19484 KB Output isn't correct
41 Correct 414 ms 21492 KB Output is correct