oj.uz

Submission #132323

# Submission time Handle Problem Language Result Execution time Memory
132323 2019-07-18T17:22:04 Z bogdan10bos 007 (CEOI14_007) C++14
0 / 100
 7 ms 5112 KB 
/// 00:04 why?
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 2e5 + 5;

int N, M, S, D, A, B;
vector<int> edg[NMAX];

vector<int> BFS(int start)
{
	vector<int> d(N + 1, 1 << 30);
	d[start] = 0;
	queue<int> q;
	q.push(start);
	while(!q.empty())
	{
		int nod = q.front();
		q.pop();
		for(auto nxt: edg[nod])
			if(d[nxt] > d[nod] + 1)
			{
				d[nxt] = d[nod] + 1;
				q.push(nxt);
			}
	}
	return d;
}

int main()
{
	freopen("1.in", "r", stdin);
	scanf("%d%d", &N, &M);
	scanf("%d%d%d%d", &S, &D, &A, &B);
	for(int i = 1; i <= M; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		edg[x].push_back(y);
		edg[y].push_back(x);
	}

	auto dS = BFS(S);
	auto dD = BFS(D);

	if(dD[A] + 1 <= dS[A] || dD[B] + 1 <= dS[B])
	{
		printf("-1\n");
		exit(0);
	}

	int timp = -1;
	if(dD[A] - dS[A] != dD[B] - dS[B])
		timp = min(dD[A] - dS[A], dD[B] - dS[B]);
	else
	{
		auto dA = BFS(A);
		auto dB = BFS(B);

		int maxStepsS = 0;
		for(int i = 1; i <= N; i++)
			if(dA[i] == dB[i] && dA[i] + dS[i] == dS[A])
				maxStepsS = max(maxStepsS, dS[i]);

		int maxStepsD = 0;
				for(int i = 1; i <= N; i++)
					if(dA[i] == dB[i] && dA[i] + dD[i] == dD[A])
						maxStepsD = max(maxStepsD, dS[i]);
		timp = min(dD[A] - dS[A], dD[B] - dS[B]);
		if(maxStepsS < maxStepsD)	timp--;
	}
	printf("%d\n", timp);
	return 0;
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:33:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("1.in", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~
007.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
007.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &S, &D, &A, &B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Incorrect 6 ms 4984 KB Output isn't correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Incorrect 6 ms 4984 KB Output isn't correct
7 Incorrect 6 ms 4984 KB Output isn't correct
8 Correct 6 ms 4984 KB Output is correct
9 Incorrect 6 ms 5112 KB Output isn't correct
10 Incorrect 6 ms 4956 KB Output isn't correct
11 Partially correct 6 ms 4984 KB Partially correct
12 Incorrect 7 ms 5028 KB Output isn't correct
13 Incorrect 6 ms 4984 KB Output isn't correct
14 Incorrect 6 ms 4984 KB Output isn't correct
15 Incorrect 6 ms 4984 KB Output isn't correct
16 Incorrect 6 ms 4984 KB Output isn't correct
17 Incorrect 7 ms 4984 KB Output isn't correct
18 Incorrect 6 ms 5036 KB Output isn't correct
19 Incorrect 6 ms 4984 KB Output isn't correct
20 Incorrect 6 ms 4984 KB Output isn't correct
21 Incorrect 6 ms 4984 KB Output isn't correct
22 Incorrect 6 ms 4984 KB Output isn't correct
23 Incorrect 6 ms 4984 KB Output isn't correct
24 Correct 6 ms 4984 KB Output is correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4984 KB Output isn't correct
2 Incorrect 6 ms 4984 KB Output isn't correct
3 Incorrect 6 ms 4984 KB Output isn't correct
4 Incorrect 6 ms 4984 KB Output isn't correct
5 Incorrect 6 ms 4984 KB Output isn't correct
6 Incorrect 6 ms 4984 KB Output isn't correct
7 Incorrect 6 ms 4984 KB Output isn't correct
8 Incorrect 6 ms 4984 KB Output isn't correct
9 Incorrect 6 ms 4956 KB Output isn't correct
10 Incorrect 6 ms 4984 KB Output isn't correct
11 Incorrect 6 ms 4956 KB Output isn't correct
12 Incorrect 6 ms 4988 KB Output isn't correct
13 Incorrect 6 ms 4984 KB Output isn't correct
14 Incorrect 6 ms 4984 KB Output isn't correct
15 Incorrect 6 ms 5112 KB Output isn't correct
16 Incorrect 6 ms 4984 KB Output isn't correct
17 Incorrect 7 ms 4988 KB Output isn't correct
18 Incorrect 6 ms 4984 KB Output isn't correct
19 Incorrect 6 ms 4984 KB Output isn't correct
20 Incorrect 6 ms 4984 KB Output isn't correct
21 Incorrect 6 ms 4984 KB Output isn't correct
22 Incorrect 6 ms 4984 KB Output isn't correct
23 Incorrect 6 ms 4984 KB Output isn't correct
24 Incorrect 6 ms 4984 KB Output isn't correct
25 Incorrect 6 ms 4984 KB Output isn't correct
26 Incorrect 6 ms 4984 KB Output isn't correct
27 Incorrect 6 ms 4984 KB Output isn't correct
28 Incorrect 6 ms 4984 KB Output isn't correct
29 Incorrect 6 ms 4960 KB Output isn't correct
30 Incorrect 6 ms 4984 KB Output isn't correct
31 Incorrect 6 ms 4984 KB Output isn't correct
32 Incorrect 7 ms 4984 KB Output isn't correct
33 Incorrect 6 ms 4984 KB Output isn't correct
34 Incorrect 6 ms 4984 KB Output isn't correct
35 Incorrect 6 ms 4984 KB Output isn't correct
36 Incorrect 6 ms 4984 KB Output isn't correct
37 Incorrect 6 ms 4984 KB Output isn't correct
38 Incorrect 6 ms 4984 KB Output isn't correct
39 Incorrect 6 ms 4984 KB Output isn't correct
40 Incorrect 6 ms 4984 KB Output isn't correct
41 Incorrect 6 ms 4984 KB Output isn't correct