Submission #30120

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
30120	2017-07-22T07:22:53 Z	cdemirer	007 (CEOI14_007)	C++14	0 / 100	923 ms	25796 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 sv1dists[200000], sv2dists[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;
				S.insert(mp(dists[edges[x.second][i]], edges[x.second][i]));
			}
		}
	}
}

int moveit(int x) {
	int cnt = 0;
	while (true) {
		bool fnd = false;
		for (int i = 0; i < edges[x].size(); i++) {
			int v = edges[x][i];
			if (sv1dists[v] == sv1dists[x]-1 && sv1dists[v] == sv2dists[v]) {
				fnd = true;
				x = v;
				break;
			}
		}
		if (!fnd) return cnt;
		else cnt++;
	}
}

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);
	}
	dijsktra(sv1dists, SV1);
	dijsktra(sv2dists, SV2);

	int ans = -1;
	ans = max(ans, min(sv1dists[D] - sv1dists[Z], sv2dists[D] - sv2dists[Z]));

	if (ans != -1 && sv1dists[D] == sv2dists[D] && sv1dists[Z] == sv2dists[Z]) {
		int a = moveit(D);
		int b = moveit(Z);
		if (a < b + ans) ans--;
	}
	printf("%d\n", ans);

	return 0;
}

Compilation message

007.cpp: In function 'void dijsktra(int*, int)':
007.cpp:32: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 moveit(int)':
007.cpp:46:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges[x].size(); i++) {
                     ^
007.cpp: In function 'int main(int, char**)':
007.cpp:64: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:65: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:69: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	3584 KB	Output is correct
2	Correct	3584 KB	Output is correct
3	Correct	3584 KB	Output is correct
4	Incorrect	3584 KB	Output isn't correct
5	Incorrect	3584 KB	Output isn't correct
6	Correct	3584 KB	Output is correct
7	Correct	3584 KB	Output is correct
8	Incorrect	3584 KB	Output isn't correct
9	Correct	3584 KB	Output is correct
10	Correct	3584 KB	Output is correct
11	Correct	3584 KB	Output is correct
12	Incorrect	3584 KB	Output isn't correct
13	Correct	3716 KB	Output is correct
14	Incorrect	3584 KB	Output isn't correct
15	Partially correct	3584 KB	Partially correct
16	Incorrect	3584 KB	Output isn't correct
17	Incorrect	3716 KB	Output isn't correct
18	Incorrect	3716 KB	Output isn't correct
19	Correct	3716 KB	Output is correct
20	Partially correct	3716 KB	Partially correct
21	Correct	3716 KB	Output is correct
22	Partially correct	3716 KB	Partially correct
23	Correct	3716 KB	Output is correct
24	Incorrect	3716 KB	Output isn't correct

Subtask #2
0.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	123 ms	7708 KB	Partially correct
2	Incorrect	186 ms	9596 KB	Output isn't correct
3	Correct	129 ms	8024 KB	Output is correct
4	Incorrect	179 ms	9780 KB	Output isn't correct
5	Correct	106 ms	7528 KB	Output is correct
6	Correct	133 ms	8200 KB	Output is correct
7	Partially correct	163 ms	8564 KB	Partially correct
8	Partially correct	156 ms	8564 KB	Partially correct
9	Incorrect	156 ms	9116 KB	Output isn't correct
10	Correct	399 ms	13996 KB	Output is correct
11	Incorrect	333 ms	12836 KB	Output isn't correct
12	Correct	449 ms	15076 KB	Output is correct
13	Incorrect	376 ms	13524 KB	Output isn't correct
14	Correct	263 ms	11984 KB	Output is correct
15	Partially correct	489 ms	15408 KB	Partially correct
16	Correct	476 ms	15952 KB	Output is correct
17	Partially correct	346 ms	14724 KB	Partially correct
18	Incorrect	429 ms	14724 KB	Output isn't correct
19	Correct	456 ms	15956 KB	Output is correct
20	Incorrect	649 ms	18952 KB	Output isn't correct
21	Incorrect	606 ms	19896 KB	Output isn't correct
22	Correct	566 ms	17660 KB	Output is correct
23	Correct	669 ms	19704 KB	Output is correct
24	Correct	673 ms	19540 KB	Output is correct
25	Incorrect	619 ms	18680 KB	Output isn't correct
26	Correct	583 ms	17844 KB	Output is correct
27	Partially correct	666 ms	19880 KB	Partially correct
28	Partially correct	699 ms	19884 KB	Partially correct
29	Correct	663 ms	19132 KB	Output is correct
30	Incorrect	753 ms	20628 KB	Output isn't correct
31	Incorrect	786 ms	22300 KB	Output isn't correct
32	Correct	653 ms	19696 KB	Output is correct
33	Correct	623 ms	20240 KB	Output is correct
34	Incorrect	736 ms	21068 KB	Output isn't correct
35	Incorrect	476 ms	20404 KB	Output isn't correct
36	Incorrect	639 ms	21080 KB	Output isn't correct
37	Correct	889 ms	23328 KB	Output is correct
38	Partially correct	686 ms	22960 KB	Partially correct
39	Partially correct	716 ms	22964 KB	Partially correct
40	Incorrect	886 ms	23936 KB	Output isn't correct
41	Correct	923 ms	25796 KB	Output is correct

Submission #30120

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