답안 #132327

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
132327	2019-07-18T17:27:31 Z	bogdan10bos	007 (CEOI14_007)	C++14	30 / 100	368 ms	17672 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, dD[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	4980 KB	Output is correct
2	Correct	6 ms	4984 KB	Output is correct
3	Correct	6 ms	4984 KB	Output is correct
4	Correct	6 ms	4984 KB	Output is correct
5	Correct	7 ms	4984 KB	Output is correct
6	Partially correct	7 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	4984 KB	Output is correct
11	Correct	6 ms	4984 KB	Output is correct
12	Correct	6 ms	5112 KB	Output is correct
13	Partially correct	6 ms	4984 KB	Partially correct
14	Correct	6 ms	4984 KB	Output is correct
15	Partially correct	7 ms	5112 KB	Partially correct
16	Correct	6 ms	5112 KB	Output is correct
17	Correct	6 ms	5112 KB	Output is correct
18	Correct	7 ms	4984 KB	Output is correct
19	Partially correct	8 ms	5112 KB	Partially correct
20	Partially correct	6 ms	5112 KB	Partially correct
21	Correct	6 ms	5112 KB	Output is correct
22	Partially correct	6 ms	5112 KB	Partially correct
23	Partially correct	6 ms	5112 KB	Partially correct
24	Correct	6 ms	4984 KB	Output is correct

Subtask #2

21.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	36 ms	6904 KB	Partially correct
2	Correct	52 ms	7800 KB	Output is correct
3	Partially correct	39 ms	7032 KB	Partially correct
4	Correct	50 ms	7928 KB	Output is correct
5	Correct	30 ms	6520 KB	Output is correct
6	Correct	31 ms	6776 KB	Output is correct
7	Partially correct	43 ms	7292 KB	Partially correct
8	Correct	42 ms	7288 KB	Output is correct
9	Correct	58 ms	7800 KB	Output is correct
10	Partially correct	193 ms	12152 KB	Partially correct
11	Correct	83 ms	9208 KB	Output is correct
12	Partially correct	116 ms	10412 KB	Partially correct
13	Correct	88 ms	9592 KB	Output is correct
14	Correct	61 ms	8288 KB	Output is correct
15	Partially correct	107 ms	10496 KB	Partially correct
16	Correct	89 ms	9848 KB	Output is correct
17	Correct	101 ms	10232 KB	Output is correct
18	Correct	109 ms	10104 KB	Output is correct
19	Partially correct	144 ms	11416 KB	Partially correct
20	Correct	251 ms	14380 KB	Output is correct
21	Correct	188 ms	12696 KB	Output is correct
22	Partially correct	164 ms	11536 KB	Partially correct
23	Correct	175 ms	12536 KB	Output is correct
24	Partially correct	173 ms	12408 KB	Partially correct
25	Correct	162 ms	11948 KB	Output is correct
26	Correct	163 ms	11812 KB	Output is correct
27	Correct	183 ms	12536 KB	Output is correct
28	Correct	193 ms	12700 KB	Output is correct
29	Partially correct	186 ms	12944 KB	Partially correct
30	Correct	281 ms	14972 KB	Output is correct
31	Correct	208 ms	13688 KB	Output is correct
32	Partially correct	185 ms	12460 KB	Partially correct
33	Correct	178 ms	12920 KB	Output is correct
34	Correct	209 ms	13264 KB	Output is correct
35	Correct	180 ms	12832 KB	Output is correct
36	Correct	201 ms	13148 KB	Output is correct
37	Correct	207 ms	12692 KB	Output is correct
38	Correct	224 ms	13920 KB	Output is correct
39	Correct	263 ms	13964 KB	Output is correct
40	Correct	268 ms	15528 KB	Output is correct
41	Partially correct	368 ms	17672 KB	Partially correct