Submission #101142

# Submission time Handle Problem Language Result Execution time Memory
101142 2019-03-17T05:20:51 Z E869120 007 (CEOI14_007) C++14
86 / 100
787 ms 62792 KB
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#pragma warning (disable: 4996)

long long N, M, p, q, a, b, dist1[1 << 18], dist2[1 << 18], dist3[1 << 18], dist4[1 << 18], dist[1 << 18]; bool used[1 << 18];
vector<int>X[1 << 18]; vector<pair<int, long long>>G[1 << 18];

vector<long long> 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<long long>vec;
	for (int i = 1; i <= N; i++) vec.push_back(dist[i]);
	return vec;
}

vector<long long> dijkstra2(int pos) {
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>>Q;
	for (int i = 1; i <= N; i++) dist[i] = (1LL << 60);
	Q.push(make_pair(0, pos)); dist[pos] = 0;

	while (!Q.empty()) {
		int pos = Q.top().second; Q.pop();
		for (int i = 0; i < G[pos].size(); i++) {
			int to = G[pos][i].first; long long cost = G[pos][i].second;
			if (dist[to] > dist[pos] + cost) {
				dist[to] = dist[pos] + cost;
				Q.push(make_pair(dist[to], to));
			}
		}
	}

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

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<long long> V1 = dijkstra(a); for (int i = 0; i < V1.size(); i++) dist1[i + 1] = V1[i];
	vector<long long> V2 = dijkstra(b); for (int i = 0; i < V2.size(); i++) dist2[i + 1] = V2[i];
	vector<long long> V3 = dijkstra(q); for (int i = 0; i < V3.size(); i++) dist3[i + 1] = V3[i];
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < X[i].size(); j++) {
			long long cost = 1000001;
			if (dist1[X[i][j]] == dist2[X[i][j]]) cost = 1000000;
			G[i].push_back(make_pair(X[i][j], cost));
		}
	}
	vector<long long> V4 = dijkstra2(a); for (int i = 0; i < V1.size(); i++) dist4[i + 1] = V4[i];

	long long minx = (1 << 30);
	for (int i = 1; i <= N; i++) {
		if (dist1[i] < dist1[p] || dist2[i] < dist2[p] || dist4[i] < dist4[p]) {
			minx = min(minx, dist3[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<long long 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 'std::vector<long long int> dijkstra2(int)':
007.cpp:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < G[pos].size(); i++) {
                   ~~^~~~~~~~~~~~~~~
007.cpp: In function 'int main()':
007.cpp:53:22: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  scanf("%d%d", &N, &M);
                ~~    ^
007.cpp:53:22: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
007.cpp:54:34: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  scanf("%d%d%d%d", &p, &q, &a, &b);
                    ~~            ^
007.cpp:54:34: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
007.cpp:54:34: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
007.cpp:54:34: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'long long int*' [-Wformat=]
007.cpp:60:56: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  vector<long long> V1 = dijkstra(a); for (int i = 0; i < V1.size(); i++) dist1[i + 1] = V1[i];
                                                      ~~^~~~~~~~~~~
007.cpp:61:56: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  vector<long long> V2 = dijkstra(b); for (int i = 0; i < V2.size(); i++) dist2[i + 1] = V2[i];
                                                      ~~^~~~~~~~~~~
007.cpp:62:56: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  vector<long long> V3 = dijkstra(q); for (int i = 0; i < V3.size(); i++) dist3[i + 1] = V3[i];
                                                      ~~^~~~~~~~~~~
007.cpp:64:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < X[i].size(); j++) {
                   ~~^~~~~~~~~~~~~
007.cpp:70:57: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  vector<long long> V4 = dijkstra2(a); for (int i = 0; i < V1.size(); i++) dist4[i + 1] = V4[i];
                                                       ~~^~~~~~~~~~~
007.cpp:53: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:54: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:56: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);
               ~~~~~^~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Partially correct 17 ms 12672 KB Partially correct
2 Correct 18 ms 12672 KB Output is correct
3 Correct 16 ms 12672 KB Output is correct
4 Correct 16 ms 12672 KB Output is correct
5 Correct 17 ms 12672 KB Output is correct
6 Correct 17 ms 12672 KB Output is correct
7 Correct 14 ms 12672 KB Output is correct
8 Correct 17 ms 12672 KB Output is correct
9 Correct 15 ms 12672 KB Output is correct
10 Partially correct 14 ms 12800 KB Partially correct
11 Correct 14 ms 12672 KB Output is correct
12 Correct 13 ms 12800 KB Output is correct
13 Correct 13 ms 12800 KB Output is correct
14 Correct 14 ms 12800 KB Output is correct
15 Correct 17 ms 12792 KB Output is correct
16 Correct 16 ms 12800 KB Output is correct
17 Correct 15 ms 12800 KB Output is correct
18 Correct 15 ms 12800 KB Output is correct
19 Correct 10 ms 12800 KB Output is correct
20 Correct 14 ms 12800 KB Output is correct
21 Correct 13 ms 12800 KB Output is correct
22 Correct 14 ms 12800 KB Output is correct
23 Correct 19 ms 12800 KB Output is correct
24 Correct 15 ms 12800 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 86 ms 18956 KB Output is correct
2 Correct 113 ms 21656 KB Output is correct
3 Correct 75 ms 19432 KB Output is correct
4 Correct 136 ms 21972 KB Output is correct
5 Correct 93 ms 18888 KB Output is correct
6 Correct 89 ms 19536 KB Output is correct
7 Correct 94 ms 20128 KB Output is correct
8 Correct 100 ms 20232 KB Output is correct
9 Correct 125 ms 22644 KB Output is correct
10 Correct 312 ms 44264 KB Output is correct
11 Correct 174 ms 26404 KB Output is correct
12 Correct 245 ms 30536 KB Output is correct
13 Correct 229 ms 27780 KB Output is correct
14 Correct 162 ms 25300 KB Output is correct
15 Correct 230 ms 30300 KB Output is correct
16 Correct 274 ms 31132 KB Output is correct
17 Correct 228 ms 29052 KB Output is correct
18 Correct 256 ms 29308 KB Output is correct
19 Correct 337 ms 35508 KB Output is correct
20 Correct 628 ms 50552 KB Output is correct
21 Correct 338 ms 37212 KB Output is correct
22 Correct 335 ms 34492 KB Output is correct
23 Correct 404 ms 37072 KB Output is correct
24 Correct 303 ms 36812 KB Output is correct
25 Correct 343 ms 35676 KB Output is correct
26 Correct 301 ms 34632 KB Output is correct
27 Correct 344 ms 37112 KB Output is correct
28 Correct 369 ms 37208 KB Output is correct
29 Correct 473 ms 42360 KB Output is correct
30 Correct 628 ms 52912 KB Output is correct
31 Correct 388 ms 40316 KB Output is correct
32 Correct 379 ms 37188 KB Output is correct
33 Correct 378 ms 38024 KB Output is correct
34 Correct 395 ms 39020 KB Output is correct
35 Correct 379 ms 37964 KB Output is correct
36 Correct 415 ms 38584 KB Output is correct
37 Correct 426 ms 41804 KB Output is correct
38 Correct 417 ms 41148 KB Output is correct
39 Correct 516 ms 41824 KB Output is correct
40 Correct 553 ms 50460 KB Output is correct
41 Correct 787 ms 62792 KB Output is correct