Submission #30118

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
30118	2017-07-22T07:20:48 Z	cdemirer	007 (CEOI14_007)	C++14	23 / 100	986 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 < Z) 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:82:7: warning: unused variable 'b' [-Wunused-variable]
   int b = moveit(Z);
       ^
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
9.0 / 30.0

#	Verdict	Memory	Grader output
1	Correct	3584 KB	Output is correct
2	Correct	3584 KB	Output is correct
3	Partially correct	3584 KB	Partially correct
4	Correct	3584 KB	Output is correct
5	Correct	3584 KB	Output is correct
6	Partially correct	3584 KB	Partially correct
7	Partially correct	3584 KB	Partially correct
8	Correct	3584 KB	Output is correct
9	Partially correct	3584 KB	Partially correct
10	Correct	3584 KB	Output is correct
11	Correct	3584 KB	Output is correct
12	Correct	3584 KB	Output is correct
13	Partially correct	3716 KB	Partially correct
14	Correct	3584 KB	Output is correct
15	Partially correct	3584 KB	Partially correct
16	Correct	3584 KB	Output is correct
17	Correct	3716 KB	Output is correct
18	Correct	3716 KB	Output is correct
19	Partially correct	3716 KB	Partially correct
20	Partially correct	3716 KB	Partially correct
21	Correct	3716 KB	Output is correct
22	Partially correct	3716 KB	Partially correct
23	Partially correct	3716 KB	Partially correct
24	Correct	3716 KB	Output is correct

Subtask #2
14.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	86 ms	7708 KB	Partially correct
2	Correct	163 ms	9596 KB	Output is correct
3	Partially correct	126 ms	8024 KB	Partially correct
4	Incorrect	159 ms	9780 KB	Output isn't correct
5	Correct	113 ms	7528 KB	Output is correct
6	Correct	116 ms	8200 KB	Output is correct
7	Partially correct	166 ms	8564 KB	Partially correct
8	Partially correct	149 ms	8564 KB	Partially correct
9	Correct	149 ms	9116 KB	Output is correct
10	Partially correct	389 ms	13996 KB	Partially correct
11	Correct	316 ms	12836 KB	Output is correct
12	Partially correct	483 ms	15076 KB	Partially correct
13	Correct	383 ms	13524 KB	Output is correct
14	Correct	286 ms	11984 KB	Output is correct
15	Partially correct	319 ms	15408 KB	Partially correct
16	Correct	316 ms	15952 KB	Output is correct
17	Partially correct	299 ms	14724 KB	Partially correct
18	Correct	403 ms	14724 KB	Output is correct
19	Partially correct	389 ms	15956 KB	Partially correct
20	Correct	603 ms	18952 KB	Output is correct
21	Correct	619 ms	19896 KB	Output is correct
22	Partially correct	559 ms	17660 KB	Partially correct
23	Correct	513 ms	19704 KB	Output is correct
24	Partially correct	479 ms	19540 KB	Partially correct
25	Correct	459 ms	18680 KB	Output is correct
26	Correct	569 ms	17844 KB	Output is correct
27	Partially correct	496 ms	19880 KB	Partially correct
28	Partially correct	563 ms	19884 KB	Partially correct
29	Partially correct	543 ms	19132 KB	Partially correct
30	Correct	743 ms	20628 KB	Output is correct
31	Correct	739 ms	22300 KB	Output is correct
32	Partially correct	773 ms	19696 KB	Partially correct
33	Correct	659 ms	20240 KB	Output is correct
34	Correct	886 ms	21068 KB	Output is correct
35	Correct	596 ms	20404 KB	Output is correct
36	Correct	536 ms	21080 KB	Output is correct
37	Correct	773 ms	23328 KB	Output is correct
38	Partially correct	909 ms	22960 KB	Partially correct
39	Partially correct	986 ms	22964 KB	Partially correct
40	Correct	899 ms	23936 KB	Output is correct
41	Partially correct	899 ms	25796 KB	Partially correct

Submission #30118

Compilation message

Subtask #1 9.0 / 30.0

Subtask #2 14.0 / 70.0

Subtask #1
9.0 / 30.0

Subtask #2
14.0 / 70.0