답안 #454809

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
454809	2021-08-05T08:29:27 Z	kingfran1907	007 (CEOI14_007)	C++14	10 / 100	285 ms	16144 KB

007

#include <bits/stdc++.h>
#define X first
#define Y second
 
using namespace std;
typedef long long llint;
 
const int maxn = 2e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 18;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, m;
int s, d, a, b;
vector< int > graph[maxn];
int disa[maxn], disb[maxn];

void calc(int x, int dis[maxn]) {
	for (int i = 1; i <= n; i++) dis[i] = -1;
	
	queue< int > q;
	dis[x] = 0;
	q.push(x);
	
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		
		for (int tren : graph[x]) {
			if (dis[tren] == -1) {
				dis[tren] = dis[x] + 1;
				q.push(tren);
			}
		}
	}
}

int f(int x) {
	int out = 0;
	while (true) {
		int ind = -1;
		for (int tren : graph[x]) {
			if (disa[tren] < disa[x] && disb[tren] < disb[x]) ind = tren;
		}
		if (ind == -1) break;
		out++;
		x = ind;
	}
	return out;
}

int main() {
	scanf("%d%d", &n, &m);
	scanf("%d%d%d%d", &s, &d, &a, &b);
	
	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	calc(a, disa);
	calc(b, disb);
	
	int ax = disa[d] - disa[s];
	int bx = disb[d] - disb[s];
	if (ax > bx) swap(ax, bx);
	
	if (ax < 0 || bx < 0) printf("-1\n");
	else if (ax + 1 == bx) printf("%d\n", ax);
	else {
		int ps = f(s);
		int pd = f(d);
		
		if (ps + ax < pd) printf("%d\n", ax - 1);
		else printf("%d\n", ax);
	}
	return 0;
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
007.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%d%d%d%d", &s, &d, &a, &b);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1

10.0 / 30.0

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

Subtask #2

0.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	6580 KB	Output is correct
2	Correct	31 ms	7244 KB	Output is correct
3	Correct	27 ms	6604 KB	Output is correct
4	Incorrect	42 ms	7336 KB	Output isn't correct
5	Partially correct	33 ms	6436 KB	Partially correct
6	Partially correct	25 ms	6748 KB	Partially correct
7	Correct	37 ms	6872 KB	Output is correct
8	Correct	26 ms	6860 KB	Output is correct
9	Correct	44 ms	7236 KB	Output is correct
10	Correct	180 ms	11624 KB	Output is correct
11	Incorrect	61 ms	8504 KB	Output isn't correct
12	Correct	77 ms	9320 KB	Output is correct
13	Incorrect	57 ms	8708 KB	Output isn't correct
14	Correct	45 ms	8236 KB	Output is correct
15	Correct	75 ms	9496 KB	Output is correct
16	Partially correct	71 ms	9668 KB	Partially correct
17	Correct	70 ms	9256 KB	Output is correct
18	Correct	83 ms	9216 KB	Output is correct
19	Correct	100 ms	10436 KB	Output is correct
20	Correct	205 ms	13192 KB	Output is correct
21	Correct	98 ms	11244 KB	Output is correct
22	Correct	98 ms	10564 KB	Output is correct
23	Correct	113 ms	11152 KB	Output is correct
24	Partially correct	89 ms	11020 KB	Partially correct
25	Incorrect	100 ms	10680 KB	Output isn't correct
26	Correct	104 ms	10480 KB	Output is correct
27	Correct	109 ms	11248 KB	Output is correct
28	Correct	113 ms	11144 KB	Output is correct
29	Correct	133 ms	11828 KB	Output is correct
30	Correct	270 ms	13764 KB	Output is correct
31	Incorrect	144 ms	12200 KB	Output isn't correct
32	Correct	117 ms	11172 KB	Output is correct
33	Correct	116 ms	11472 KB	Output is correct
34	Incorrect	128 ms	11624 KB	Output isn't correct
35	Incorrect	124 ms	11404 KB	Output isn't correct
36	Incorrect	104 ms	11704 KB	Output isn't correct
37	Partially correct	135 ms	12512 KB	Partially correct
38	Correct	134 ms	12416 KB	Output is correct
39	Correct	140 ms	12420 KB	Output is correct
40	Correct	212 ms	13888 KB	Output is correct
41	Correct	285 ms	16144 KB	Output is correct