Submission #30063

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
30063	2017-07-21T23:15:17 Z	cdemirer	007 (CEOI14_007)	C++14	40.3333 / 100	906 ms	27752 KB

007

#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], Zparents[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;
				else Zparents[edges[x.second][i]] = x.second;
				S.insert(mp(dists[edges[x.second][i]], edges[x.second][i]));
			}
		}
	}
}

bool flagD[200000] = {0};
bool flagZ[200000] = {0};

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);
	Zparents[Z] = -1;
	dijsktra(Zdists, Z);

	int ans = -1;
	if (Ddists[SV1] == Ddists[SV2]) {
		int svd = min(Ddists[SV1]-Zdists[SV1], Ddists[SV2]-Zdists[SV2]);
		ans = max(ans, svd);
		if (Zdists[SV1] == Zdists[SV2]) {
			int fakeD = 0, fakeZ = 0;
			int x = SV1;
			while (x != -1) {
				flagD[x] = true;
				x = Dparents[x];
			}
			x = SV2;
			while (x != -1) {
				if (!flagD[x]) fakeD++;
				else break;
				x = Dparents[x];
			}
			x = SV1;
			while (x != -1) {
				flagZ[x] = true;
				x = Zparents[x];
			}
			x = SV2;
			while (x != -1) {
				if (!flagZ[x]) fakeZ++;
				else break;
				x = Zparents[x];
			}
			if (fakeD < fakeZ) {
				if (ans != -1) ans--;
			}
		}
	}
	else {
		if (Ddists[SV1] < Ddists[SV2]) {
			ans = max(ans, Ddists[SV1] - Zdists[SV1]);
		}
		else {
			ans = max(ans, Ddists[SV2] - Zdists[SV2]);
		}
	}
	printf("%d\n", ans);

	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:53: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:54: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:58: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

10.0 / 30.0

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

Subtask #2

30.333333 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	113 ms	9664 KB	Output is correct
2	Correct	156 ms	11552 KB	Output is correct
3	Partially correct	119 ms	9980 KB	Partially correct
4	Correct	169 ms	11736 KB	Output is correct
5	Correct	103 ms	9484 KB	Output is correct
6	Correct	119 ms	10156 KB	Output is correct
7	Correct	169 ms	10520 KB	Output is correct
8	Correct	156 ms	10520 KB	Output is correct
9	Correct	149 ms	11072 KB	Output is correct
10	Correct	356 ms	15952 KB	Output is correct
11	Correct	329 ms	14792 KB	Output is correct
12	Correct	443 ms	17032 KB	Output is correct
13	Correct	346 ms	15480 KB	Output is correct
14	Correct	249 ms	13940 KB	Output is correct
15	Correct	306 ms	17364 KB	Output is correct
16	Correct	443 ms	17908 KB	Output is correct
17	Correct	396 ms	16680 KB	Output is correct
18	Correct	406 ms	16680 KB	Output is correct
19	Correct	473 ms	17912 KB	Output is correct
20	Correct	499 ms	20908 KB	Output is correct
21	Incorrect	606 ms	21852 KB	Output isn't correct
22	Partially correct	556 ms	19616 KB	Partially correct
23	Correct	583 ms	21660 KB	Output is correct
24	Partially correct	616 ms	21496 KB	Partially correct
25	Incorrect	483 ms	20636 KB	Output isn't correct
26	Correct	556 ms	19800 KB	Output is correct
27	Correct	679 ms	21836 KB	Output is correct
28	Correct	716 ms	21840 KB	Output is correct
29	Correct	576 ms	21088 KB	Output is correct
30	Correct	689 ms	22584 KB	Output is correct
31	Incorrect	763 ms	24256 KB	Output isn't correct
32	Correct	663 ms	21652 KB	Output is correct
33	Correct	663 ms	22196 KB	Output is correct
34	Incorrect	749 ms	23024 KB	Output isn't correct
35	Correct	646 ms	22360 KB	Output is correct
36	Correct	669 ms	23036 KB	Output is correct
37	Correct	846 ms	25284 KB	Output is correct
38	Correct	829 ms	24916 KB	Output is correct
39	Correct	839 ms	24920 KB	Output is correct
40	Correct	846 ms	25892 KB	Output is correct
41	Correct	906 ms	27752 KB	Output is correct