oj.uz

Submission #30123

# Submission time Handle Problem Language Result Execution time Memory
30123 2017-07-22T07:31:40 Z cdemirer 007 (CEOI14_007) C++14
0 / 100
 1000 ms 413620 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];
bool vis1[200000] = {0};
bool vis2[200000] = {0};

void bfs(int *dists, bool *vis, int x) {
	queue<int> Q;
	queue<int> Qt;
	int d = 0;
	Q.push(x);
	while (!Q.empty()) {
		while (!Q.empty()) {
			int x = Q.front();
			Q.pop();
			dists[x] = d;
			vis[x] = true;
			for (int i = 0; i < edges[x].size(); i++) {
				if (vis[edges[x][i]]) continue;
				Qt.push(edges[x][i]);
			}
		}
		while (!Qt.empty()) {
			int x = Qt.front();
			Qt.pop();
			Q.push(x);
		}
		d++;
	}
}

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);
	}
	bfs(sv1dists, vis1, SV1);
	bfs(sv2dists, vis2, 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 bfs(int*, bool*, int)':
007.cpp:31:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < edges[x].size(); i++) {
                      ^
007.cpp: In function 'int moveit(int)':
007.cpp:49: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:67: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:68: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:72: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 Execution time Memory Grader output
1 Incorrect 0 ms 3976 KB Output isn't correct
2 Incorrect 0 ms 3976 KB Output isn't correct
3 Correct 0 ms 3976 KB Output is correct
4 Correct 0 ms 3976 KB Output is correct
5 Correct 0 ms 3976 KB Output is correct
6 Correct 0 ms 3976 KB Output is correct
7 Partially correct 0 ms 3976 KB Partially correct
8 Correct 0 ms 3976 KB Output is correct
9 Correct 0 ms 3976 KB Output is correct
10 Incorrect 0 ms 3976 KB Output isn't correct
11 Partially correct 0 ms 3976 KB Partially correct
12 Correct 0 ms 3976 KB Output is correct
13 Correct 0 ms 3976 KB Output is correct
14 Correct 0 ms 3976 KB Output is correct
15 Correct 0 ms 3976 KB Output is correct
16 Correct 356 ms 28064 KB Output is correct
17 Correct 0 ms 3976 KB Output is correct
18 Correct 0 ms 3976 KB Output is correct
19 Correct 0 ms 3976 KB Output is correct
20 Correct 0 ms 3976 KB Output is correct
21 Correct 0 ms 3976 KB Output is correct
22 Correct 0 ms 3976 KB Output is correct
23 Correct 0 ms 3976 KB Output is correct
24 Execution timed out 1000 ms 147104 KB Execution timed out

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6252 KB Output is correct
2 Correct 33 ms 7216 KB Output is correct
3 Correct 23 ms 6304 KB Output is correct
4 Correct 43 ms 7400 KB Output is correct
5 Correct 43 ms 6072 KB Output is correct
6 Correct 26 ms 6480 KB Output is correct
7 Correct 26 ms 6712 KB Output is correct
8 Partially correct 36 ms 6712 KB Partially correct
9 Execution timed out 1000 ms 222056 KB Execution timed out
10 Execution timed out 1000 ms 413620 KB Execution timed out
11 Correct 79 ms 9004 KB Output is correct
12 Correct 103 ms 10188 KB Output is correct
13 Correct 109 ms 9296 KB Output is correct
14 Correct 63 ms 8548 KB Output is correct
15 Correct 99 ms 10388 KB Output is correct
16 Correct 99 ms 10668 KB Output is correct
17 Correct 86 ms 9968 KB Output is correct
18 Correct 83 ms 9968 KB Output is correct
19 Execution timed out 1000 ms 228136 KB Execution timed out
20 Execution timed out 1000 ms 309908 KB Execution timed out
21 Correct 86 ms 12764 KB Output is correct
22 Correct 139 ms 11584 KB Output is correct
23 Incorrect 159 ms 12704 KB Output isn't correct
24 Correct 159 ms 12540 KB Output is correct
25 Correct 126 ms 12076 KB Output is correct
26 Incorrect 133 ms 11636 KB Output isn't correct
27 Correct 139 ms 12748 KB Output is correct
28 Correct 149 ms 12752 KB Output is correct
29 Execution timed out 1000 ms 242172 KB Execution timed out
30 Execution timed out 1000 ms 262776 KB Execution timed out
31 Correct 153 ms 14112 KB Output is correct
32 Correct 173 ms 12696 KB Output is correct
33 Incorrect 159 ms 12976 KB Output isn't correct
34 Correct 189 ms 13408 KB Output is correct
35 Correct 169 ms 13008 KB Output is correct
36 Correct 173 ms 13420 KB Output is correct
37 Correct 179 ms 14612 KB Output is correct
38 Correct 173 ms 14376 KB Output is correct
39 Correct 196 ms 14380 KB Output is correct
40 Execution timed out 1000 ms 235944 KB Execution timed out
41 Execution timed out 1000 ms 247064 KB Execution timed out