Submission #30064

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
30064	2017-07-21T23:35:43 Z	cdemirer	007 (CEOI14_007)	C++14	0 / 100	883 ms	27752 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], 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 + (svd!=-1?svd:0) < 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
0.0 / 30.0

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

Subtask #2
0.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	116 ms	9664 KB	Output is correct
2	Incorrect	166 ms	11552 KB	Output isn't correct
3	Partially correct	113 ms	9980 KB	Partially correct
4	Incorrect	153 ms	11736 KB	Output isn't correct
5	Correct	96 ms	9484 KB	Output is correct
6	Correct	123 ms	10156 KB	Output is correct
7	Correct	149 ms	10520 KB	Output is correct
8	Correct	139 ms	10520 KB	Output is correct
9	Incorrect	153 ms	11072 KB	Output isn't correct
10	Correct	349 ms	15952 KB	Output is correct
11	Correct	316 ms	14792 KB	Output is correct
12	Correct	433 ms	17032 KB	Output is correct
13	Incorrect	339 ms	15480 KB	Output isn't correct
14	Correct	276 ms	13940 KB	Output is correct
15	Correct	426 ms	17364 KB	Output is correct
16	Correct	463 ms	17908 KB	Output is correct
17	Correct	379 ms	16680 KB	Output is correct
18	Incorrect	406 ms	16680 KB	Output isn't correct
19	Correct	423 ms	17912 KB	Output is correct
20	Incorrect	586 ms	20908 KB	Output isn't correct
21	Incorrect	613 ms	21852 KB	Output isn't correct
22	Correct	523 ms	19616 KB	Output is correct
23	Correct	593 ms	21660 KB	Output is correct
24	Correct	636 ms	21496 KB	Output is correct
25	Incorrect	606 ms	20636 KB	Output isn't correct
26	Correct	489 ms	19800 KB	Output is correct
27	Correct	519 ms	21836 KB	Output is correct
28	Correct	723 ms	21840 KB	Output is correct
29	Correct	546 ms	21088 KB	Output is correct
30	Incorrect	599 ms	22584 KB	Output isn't correct
31	Incorrect	643 ms	24256 KB	Output isn't correct
32	Correct	696 ms	21652 KB	Output is correct
33	Correct	669 ms	22196 KB	Output is correct
34	Incorrect	806 ms	23024 KB	Output isn't correct
35	Incorrect	653 ms	22360 KB	Output isn't correct
36	Correct	629 ms	23036 KB	Output is correct
37	Correct	813 ms	25284 KB	Output is correct
38	Correct	866 ms	24916 KB	Output is correct
39	Correct	863 ms	24920 KB	Output is correct
40	Incorrect	766 ms	25892 KB	Output isn't correct
41	Correct	883 ms	27752 KB	Output is correct

Submission #30064

Compilation message

Subtask #1 0.0 / 30.0

Subtask #2 0.0 / 70.0

Subtask #1
0.0 / 30.0

Subtask #2
0.0 / 70.0