oj.uz

Submission #29834

# Submission time Handle Problem Language Result Execution time Memory
29834 2017-07-21T08:08:00 Z cdemirer 007 (CEOI14_007) C++14
0 / 100
 849 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] - 2);
	if (Dparents[SV2] == SV1) best2 = max(best2, Ddists[SV2] - Zdists[SV2] - 2);
	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 99 ms 8492 KB Output isn't correct
2 Partially correct 186 ms 10380 KB Partially correct
3 Incorrect 139 ms 8808 KB Output isn't correct
4 Partially correct 163 ms 10564 KB Partially correct
5 Correct 109 ms 8312 KB Output is correct
6 Correct 139 ms 8984 KB Output is correct
7 Correct 143 ms 9348 KB Output is correct
8 Correct 109 ms 9348 KB Output is correct
9 Partially correct 116 ms 9900 KB Partially correct
10 Incorrect 263 ms 14780 KB Output isn't correct
11 Partially correct 236 ms 13620 KB Partially correct
12 Incorrect 473 ms 15860 KB Output isn't correct
13 Partially correct 386 ms 14308 KB Partially correct
14 Correct 283 ms 12768 KB Output is correct
15 Incorrect 426 ms 16192 KB Output isn't correct
16 Incorrect 416 ms 16736 KB Output isn't correct
17 Correct 399 ms 15508 KB Output is correct
18 Incorrect 413 ms 15508 KB Output isn't correct
19 Incorrect 453 ms 16740 KB Output isn't correct
20 Partially correct 589 ms 19736 KB Partially correct
21 Partially correct 569 ms 20680 KB Partially correct
22 Incorrect 483 ms 18444 KB Output isn't correct
23 Partially correct 516 ms 20488 KB Partially correct
24 Incorrect 383 ms 20324 KB Output isn't correct
25 Partially correct 473 ms 19464 KB Partially correct
26 Partially correct 513 ms 18628 KB Partially correct
27 Correct 656 ms 20664 KB Output is correct
28 Incorrect 633 ms 20668 KB Output isn't correct
29 Incorrect 476 ms 19916 KB Output isn't correct
30 Partially correct 716 ms 21412 KB Partially correct
31 Partially correct 623 ms 23084 KB Partially correct
32 Incorrect 736 ms 20480 KB Output isn't correct
33 Partially correct 723 ms 21024 KB Partially correct
34 Partially correct 696 ms 21852 KB Partially correct
35 Partially correct 663 ms 21188 KB Partially correct
36 Partially correct 616 ms 21864 KB Partially correct
37 Incorrect 766 ms 24112 KB Output isn't correct
38 Correct 699 ms 23744 KB Output is correct
39 Correct 643 ms 23748 KB Output is correct
40 Partially correct 673 ms 24720 KB Partially correct
41 Incorrect 849 ms 26580 KB Output isn't correct