답안 #30121 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30121	2017-07-22T07:24:17 Z	cdemirer	007 (CEOI14_007)	C++14	76.6667 / 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 (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
30.0 / 30.0

#	결과	메모리	Grader output
1	Correct	3584 KB	Output is correct
2	Correct	3584 KB	Output is correct
3	Correct	3584 KB	Output is correct
4	Correct	3584 KB	Output is correct
5	Correct	3584 KB	Output is correct
6	Correct	3584 KB	Output is correct
7	Correct	3584 KB	Output is correct
8	Correct	3584 KB	Output is correct
9	Correct	3584 KB	Output is correct
10	Correct	3584 KB	Output is correct
11	Correct	3584 KB	Output is correct
12	Correct	3584 KB	Output is correct
13	Correct	3716 KB	Output is correct
14	Correct	3584 KB	Output is correct
15	Correct	3584 KB	Output is correct
16	Correct	3584 KB	Output is correct
17	Correct	3716 KB	Output is correct
18	Correct	3716 KB	Output is 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	Correct	3716 KB	Output is correct

Subtask #2
46.666667 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	113 ms	7708 KB	Output is correct
2	Correct	179 ms	9596 KB	Output is correct
3	Correct	123 ms	8024 KB	Output is correct
4	Correct	166 ms	9780 KB	Output is correct
5	Correct	113 ms	7528 KB	Output is correct
6	Correct	119 ms	8200 KB	Output is correct
7	Correct	143 ms	8564 KB	Output is correct
8	Correct	156 ms	8564 KB	Output is correct
9	Correct	166 ms	9116 KB	Output is correct
10	Correct	329 ms	13996 KB	Output is correct
11	Correct	326 ms	12836 KB	Output is correct
12	Correct	476 ms	15076 KB	Output is correct
13	Correct	383 ms	13524 KB	Output is correct
14	Correct	289 ms	11984 KB	Output is correct
15	Correct	473 ms	15408 KB	Output is correct
16	Correct	513 ms	15952 KB	Output is correct
17	Correct	439 ms	14724 KB	Output is correct
18	Correct	449 ms	14724 KB	Output is correct
19	Correct	516 ms	15956 KB	Output is correct
20	Correct	653 ms	18952 KB	Output is correct
21	Correct	683 ms	19896 KB	Output is correct
22	Correct	629 ms	17660 KB	Output is correct
23	Correct	646 ms	19704 KB	Output is correct
24	Correct	656 ms	19540 KB	Output is correct
25	Correct	583 ms	18680 KB	Output is correct
26	Correct	546 ms	17844 KB	Output is correct
27	Correct	699 ms	19880 KB	Output is correct
28	Correct	633 ms	19884 KB	Output is correct
29	Correct	516 ms	19132 KB	Output is correct
30	Correct	743 ms	20628 KB	Output is correct
31	Correct	763 ms	22300 KB	Output is correct
32	Correct	613 ms	19696 KB	Output is correct
33	Correct	609 ms	20240 KB	Output is correct
34	Correct	683 ms	21068 KB	Output is correct
35	Correct	549 ms	20404 KB	Output is correct
36	Correct	489 ms	21080 KB	Output is correct
37	Correct	856 ms	23328 KB	Output is correct
38	Correct	863 ms	22960 KB	Output is correct
39	Correct	789 ms	22964 KB	Output is correct
40	Correct	643 ms	23936 KB	Output is correct
41	Execution timed out	1000 ms	25796 KB	Execution timed out

답안 #30121

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 46.666667 / 70.0

Subtask #1
30.0 / 30.0

Subtask #2
46.666667 / 70.0