Submission #30119

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
30119	2017-07-22T07:21:34 Z	cdemirer	007 (CEOI14_007)	C++14	0 / 100	1000 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 (ans + a < b) 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	Correct	3584 KB	Output is 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	Correct	3716 KB	Output is correct
21	Correct	3716 KB	Output is correct
22	Correct	3716 KB	Output is 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	Correct	119 ms	7708 KB	Output is correct
2	Incorrect	179 ms	9596 KB	Output isn't correct
3	Correct	133 ms	8024 KB	Output is correct
4	Incorrect	186 ms	9780 KB	Output isn't correct
5	Correct	113 ms	7528 KB	Output is correct
6	Correct	123 ms	8200 KB	Output is correct
7	Correct	156 ms	8564 KB	Output is correct
8	Partially correct	149 ms	8564 KB	Partially correct
9	Incorrect	149 ms	9116 KB	Output isn't correct
10	Correct	366 ms	13996 KB	Output is correct
11	Incorrect	306 ms	12836 KB	Output isn't correct
12	Correct	483 ms	15076 KB	Output is correct
13	Incorrect	373 ms	13524 KB	Output isn't correct
14	Correct	283 ms	11984 KB	Output is correct
15	Correct	419 ms	15408 KB	Output is correct
16	Correct	493 ms	15952 KB	Output is correct
17	Correct	413 ms	14724 KB	Output is correct
18	Incorrect	446 ms	14724 KB	Output isn't correct
19	Correct	493 ms	15956 KB	Output is correct
20	Incorrect	626 ms	18952 KB	Output isn't correct
21	Incorrect	629 ms	19896 KB	Output isn't correct
22	Correct	546 ms	17660 KB	Output is correct
23	Correct	639 ms	19704 KB	Output is correct
24	Correct	589 ms	19540 KB	Output is correct
25	Incorrect	556 ms	18680 KB	Output isn't correct
26	Correct	559 ms	17844 KB	Output is correct
27	Correct	679 ms	19880 KB	Output is correct
28	Partially correct	499 ms	19884 KB	Partially correct
29	Correct	539 ms	19132 KB	Output is correct
30	Incorrect	706 ms	20628 KB	Output isn't correct
31	Incorrect	613 ms	22300 KB	Output isn't correct
32	Correct	549 ms	19696 KB	Output is correct
33	Correct	686 ms	20240 KB	Output is correct
34	Incorrect	796 ms	21068 KB	Output isn't correct
35	Incorrect	686 ms	20404 KB	Output isn't correct
36	Incorrect	689 ms	21080 KB	Output isn't correct
37	Correct	863 ms	23328 KB	Output is correct
38	Correct	909 ms	22960 KB	Output is correct
39	Correct	869 ms	22964 KB	Output is correct
40	Incorrect	849 ms	23936 KB	Output isn't correct
41	Execution timed out	1000 ms	25796 KB	Execution timed out

Submission #30119

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