oj.uz

Submission #29964

# Submission time Handle Problem Language Result Execution time Memory
29964 2017-07-21T11:30:24 Z cdemirer 007 (CEOI14_007) C++14
0 / 100
 0 ms 4372 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 Ddists[200000], Zdists[200000];
int Dparents[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;
				if (s == D) Dparents[edges[x.second][i]] = x.second;
				S.insert(mp(dists[edges[x.second][i]], edges[x.second][i]));
			}
		}
	}
}

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);
	}
	Dparents[D] = -1;
	dijsktra(Ddists, D);
	dijsktra(Zdists, Z);

	int best1 = -1;
	int best2 = -1;
	int x = Dparents[SV1];
	while (x != -1) {
		//if (x) cerr << x << endl;
		int fark = Ddists[x] - Zdists[x];
		best1 = max(best1, fark);
		x = Dparents[x];
	}
	x = Dparents[SV2];
	while (x != -1) {
		int fark = Ddists[x] - Zdists[x];
		best2 = max(best2, fark);
		x = Dparents[x];
	}
	int sv1 = Ddists[SV1] - Zdists[SV1];
	int sv2 = Ddists[SV2] - Zdists[SV2];
	int minsv = min(sv1, sv2);
	int ans = -1;
	ans = max(ans, min(best1, best2));
	ans = max(ans, minsv);
	//if (Dparents[SV1] == SV2) best1 = max(best1, Ddists[SV1] - Zdists[SV1] - 2);
	//if (Dparents[SV2] == SV1) best2 = max(best2, Ddists[SV2] - Zdists[SV2] - 2);
	//int ans = min(best1, best2);
	if (Dparents[SV1] != Dparents[SV2] && min(best1, best2) != ans) ans = (ans!=-1?ans-1:-1);
	printf("%d\n", (ans!=-1?ans:-1));

	return 0;
}

Compilation message

007.cpp: In function 'void dijsktra(int*, int)':
007.cpp:33: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 main(int, char**)':
007.cpp:46:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("input", "r", stdin);
                              ^
007.cpp:47:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("output", "w", stdout);
                                ^
007.cpp:49: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:50: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:54: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 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
2 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
3 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
4 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
5 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
6 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
7 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
8 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
9 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
10 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
11 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
12 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
13 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
14 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
15 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
16 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
17 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
18 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
19 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
20 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
21 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
22 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
23 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
24 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
2 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
3 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
4 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
5 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
6 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
7 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
8 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
9 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
10 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
11 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
12 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
13 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
14 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
15 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
16 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
17 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
18 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
19 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
20 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
21 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
22 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
23 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
24 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
25 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
26 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
27 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
28 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
29 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
30 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
31 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
32 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
33 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
34 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
35 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
36 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
37 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
38 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
39 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
40 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)
41 Runtime error 0 ms 4372 KB Execution killed because of forbidden syscall [unknown syscall - gap in table] (292)