oj.uz

Submission #29833

# Submission time Handle Problem Language Result Execution time Memory
29833 2017-07-21T08:06:23 Z cdemirer 007 (CEOI14_007) C++14
0 / 100
 919 ms 26580 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> llp;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

int N, M;
int Z, D, SV1, SV2;
vvi edges;
int Ddists[200000], Zdists[200000];
int Dparents[200000];

void dijsktra(int *dists, int s) {
	set<ii> S;
	for (int i = 0; i < N; i++) {
		if (i == s) {
			dists[i] = 0;
			S.insert(mp(dists[i], i));
			continue;
		}
		dists[i] = (int)1e9;
		S.insert(mp(dists[i], i));
	}
	while ( ! S.empty() ) {
		ii x = *S.begin();
		S.erase(S.begin());
		for (int i = 0; i < edges[x.second].size(); i++) {
			if (dists[x.second] + 1 < dists[edges[x.second][i]]) {
				S.erase(mp(dists[edges[x.second][i]], edges[x.second][i]));
				dists[edges[x.second][i]] = dists[x.second] + 1;
				if (s == D) Dparents[edges[x.second][i]] = x.second;
				S.insert(mp(dists[edges[x.second][i]], edges[x.second][i]));
			}
		}
	}
}

int main(int argc, char **argv) {

	//freopen("input", "r", stdin);
	//freopen("output", "w", stdout);

	scanf("%d%d", &N, &M);
	scanf("%d%d%d%d", &Z, &D, &SV1, &SV2);
	Z--; D--; SV1--; SV2--;
	edges.resize(N);
	for (int i = 0; i < M; i++) {
		int a, b; scanf("%d%d", &a, &b);
		a--, b--;
		edges[a].pb(b);
		edges[b].pb(a);
	}
	Dparents[D] = -1;
	dijsktra(Ddists, D);
	dijsktra(Zdists, Z);

	int best1 = -1;
	int best2 = -1;
	int x = Dparents[SV1];
	while (x != -1) {
		//if (x) cerr << x << endl;
		int fark = Ddists[x] - Zdists[x];
		best1 = max(best1, fark);
		x = Dparents[x];
	}
	x = Dparents[SV2];
	while (x != -1) {
		int fark = Ddists[x] - Zdists[x];
		best2 = max(best2, fark);
		x = Dparents[x];
	}
	if (Dparents[SV1] == SV2) best1 = max(best1, Ddists[SV1] - Zdists[SV1] - 1);
	if (Dparents[SV2] == SV1) best2 = max(best2, Ddists[SV2] - Zdists[SV2] - 1);
	int ans = min(best1, best2);
	printf("%d\n", (ans!=-1?ans:-1));

	return 0;
}

Compilation message

007.cpp: In function 'void dijsktra(int*, int)':
007.cpp:33:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges[x.second].size(); i++) {
                     ^
007.cpp: In function 'int main(int, char**)':
007.cpp:49:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
007.cpp:50:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &Z, &D, &SV1, &SV2);
                                       ^
007.cpp:54:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
                                  ^

Subtask #1
0.0 / 30.0

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

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 8492 KB Output isn't correct
2 Partially correct 163 ms 10380 KB Partially correct
3 Incorrect 83 ms 8808 KB Output isn't correct
4 Partially correct 129 ms 10564 KB Partially correct
5 Correct 113 ms 8312 KB Output is correct
6 Correct 119 ms 8984 KB Output is correct
7 Correct 159 ms 9348 KB Output is correct
8 Correct 166 ms 9348 KB Output is correct
9 Partially correct 176 ms 9900 KB Partially correct
10 Incorrect 343 ms 14780 KB Output isn't correct
11 Partially correct 333 ms 13620 KB Partially correct
12 Incorrect 466 ms 15860 KB Output isn't correct
13 Partially correct 363 ms 14308 KB Partially correct
14 Correct 259 ms 12768 KB Output is correct
15 Incorrect 403 ms 16192 KB Output isn't correct
16 Incorrect 419 ms 16736 KB Output isn't correct
17 Correct 453 ms 15508 KB Output is correct
18 Incorrect 349 ms 15508 KB Output isn't correct
19 Incorrect 379 ms 16740 KB Output isn't correct
20 Partially correct 493 ms 19736 KB Partially correct
21 Partially correct 559 ms 20680 KB Partially correct
22 Incorrect 496 ms 18444 KB Output isn't correct
23 Partially correct 643 ms 20488 KB Partially correct
24 Incorrect 599 ms 20324 KB Output isn't correct
25 Partially correct 569 ms 19464 KB Partially correct
26 Partially correct 523 ms 18628 KB Partially correct
27 Correct 566 ms 20664 KB Output is correct
28 Incorrect 463 ms 20668 KB Output isn't correct
29 Incorrect 593 ms 19916 KB Output isn't correct
30 Partially correct 563 ms 21412 KB Partially correct
31 Partially correct 616 ms 23084 KB Partially correct
32 Incorrect 566 ms 20480 KB Output isn't correct
33 Partially correct 606 ms 21024 KB Partially correct
34 Partially correct 533 ms 21852 KB Partially correct
35 Partially correct 666 ms 21188 KB Partially correct
36 Partially correct 626 ms 21864 KB Partially correct
37 Incorrect 723 ms 24112 KB Output isn't correct
38 Correct 683 ms 23744 KB Output is correct
39 Correct 723 ms 23748 KB Output is correct
40 Partially correct 629 ms 24720 KB Partially correct
41 Incorrect 919 ms 26580 KB Output isn't correct