답안 #132324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
132324	2019-07-18T17:23:30 Z	bogdan10bos	007 (CEOI14_007)	C++14	30 / 100	367 ms	25100 KB

007

/// 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: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

9.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4984 KB	Output is correct
2	Correct	6 ms	4984 KB	Output is correct
3	Partially correct	6 ms	4984 KB	Partially correct
4	Correct	6 ms	4984 KB	Output is correct
5	Correct	8 ms	4984 KB	Output is correct
6	Partially correct	8 ms	4984 KB	Partially correct
7	Partially correct	6 ms	4984 KB	Partially correct
8	Correct	6 ms	4984 KB	Output is correct
9	Partially correct	6 ms	4984 KB	Partially correct
10	Correct	6 ms	5112 KB	Output is correct
11	Correct	7 ms	4984 KB	Output is correct
12	Correct	8 ms	5112 KB	Output is correct
13	Partially correct	6 ms	4984 KB	Partially correct
14	Correct	7 ms	4984 KB	Output is correct
15	Partially correct	8 ms	5084 KB	Partially correct
16	Correct	6 ms	4984 KB	Output is correct
17	Correct	8 ms	5112 KB	Output is correct
18	Correct	6 ms	4984 KB	Output is correct
19	Partially correct	6 ms	4984 KB	Partially correct
20	Partially correct	7 ms	5112 KB	Partially correct
21	Correct	7 ms	5112 KB	Output is correct
22	Partially correct	7 ms	5112 KB	Partially correct
23	Partially correct	7 ms	5112 KB	Partially correct
24	Correct	8 ms	5112 KB	Output is correct

Subtask #2

21.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	35 ms	7416 KB	Partially correct
2	Correct	62 ms	8512 KB	Output is correct
3	Partially correct	39 ms	7548 KB	Partially correct
4	Correct	52 ms	8696 KB	Output is correct
5	Correct	32 ms	7056 KB	Output is correct
6	Correct	32 ms	7292 KB	Output is correct
7	Partially correct	44 ms	7928 KB	Partially correct
8	Partially correct	44 ms	7900 KB	Partially correct
9	Correct	59 ms	8696 KB	Output is correct
10	Partially correct	198 ms	16988 KB	Partially correct
11	Correct	89 ms	10360 KB	Output is correct
12	Partially correct	123 ms	11896 KB	Partially correct
13	Correct	94 ms	10744 KB	Output is correct
14	Correct	63 ms	9208 KB	Output is correct
15	Partially correct	133 ms	11976 KB	Partially correct
16	Correct	102 ms	11256 KB	Output is correct
17	Partially correct	115 ms	11512 KB	Partially correct
18	Correct	122 ms	11384 KB	Output is correct
19	Partially correct	144 ms	13948 KB	Partially correct
20	Correct	258 ms	19216 KB	Output is correct
21	Correct	184 ms	14584 KB	Output is correct
22	Partially correct	161 ms	13304 KB	Partially correct
23	Correct	187 ms	14456 KB	Output is correct
24	Partially correct	173 ms	14368 KB	Partially correct
25	Correct	155 ms	13816 KB	Output is correct
26	Correct	143 ms	13432 KB	Output is correct
27	Partially correct	171 ms	14456 KB	Partially correct
28	Partially correct	186 ms	14608 KB	Partially correct
29	Partially correct	184 ms	16376 KB	Partially correct
30	Correct	266 ms	19780 KB	Output is correct
31	Correct	224 ms	15992 KB	Output is correct
32	Partially correct	245 ms	14616 KB	Partially correct
33	Correct	193 ms	14968 KB	Output is correct
34	Correct	206 ms	15352 KB	Output is correct
35	Correct	185 ms	14968 KB	Output is correct
36	Correct	186 ms	15352 KB	Output is correct
37	Correct	168 ms	15068 KB	Output is correct
38	Partially correct	227 ms	16580 KB	Partially correct
39	Partially correct	260 ms	16348 KB	Partially correct
40	Correct	269 ms	20088 KB	Output is correct
41	Partially correct	367 ms	25100 KB	Partially correct