Submission #455034

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
455034	2021-08-05T11:45:47 Z	kingfran1907	007 (CEOI14_007)	C++14	30 / 100	329 ms	21180 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];
int dp[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);
			}
		}
	}
}

bool cmp(int a, int b) {
	return disa[a] < disa[b];
}

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);
	
	vector< int > v;
	for (int i = 1; i <= n; i++) v.push_back(i);
	sort(v.begin(), v.end(), cmp);
	
	for (int i : v) {
		dp[i] = 0;
		for (int tren : graph[i]) {
			if (disa[i] > disa[tren] && disb[i] > disb[tren]) dp[i] = max(dp[i], 1 + dp[tren]);
		}
	}
	
	if (disa[s] != disb[s] || disa[d] != disb[d]) {
		int sol = min(disa[d] - disa[s], disb[d] - disb[s]);
		printf("%d\n", max(sol, -1));
	} else {
		int sol = disa[d] - disa[s] - 1;
		printf("%d\n", max(sol, -1));
	}
	return 0;
}

Compilation message

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

Subtask #1

9.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4940 KB	Output is correct
2	Correct	3 ms	4940 KB	Output is correct
3	Partially correct	3 ms	4940 KB	Partially correct
4	Correct	3 ms	4940 KB	Output is correct
5	Correct	3 ms	4996 KB	Output is correct
6	Partially correct	4 ms	4940 KB	Partially correct
7	Partially correct	3 ms	4940 KB	Partially correct
8	Correct	3 ms	4940 KB	Output is correct
9	Partially correct	3 ms	4940 KB	Partially correct
10	Correct	3 ms	4940 KB	Output is correct
11	Correct	3 ms	4996 KB	Output is correct
12	Correct	3 ms	4940 KB	Output is correct
13	Partially correct	3 ms	5000 KB	Partially correct
14	Correct	4 ms	4940 KB	Output is correct
15	Partially correct	3 ms	4940 KB	Partially correct
16	Correct	4 ms	4940 KB	Output is correct
17	Correct	3 ms	4940 KB	Output is correct
18	Correct	4 ms	4940 KB	Output is correct
19	Partially correct	4 ms	4940 KB	Partially correct
20	Partially correct	4 ms	4940 KB	Partially correct
21	Correct	3 ms	5020 KB	Output is correct
22	Partially correct	4 ms	5000 KB	Partially correct
23	Partially correct	4 ms	4940 KB	Partially correct
24	Correct	4 ms	5068 KB	Output is correct

Subtask #2

21.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	29 ms	7436 KB	Partially correct
2	Correct	39 ms	8488 KB	Output is correct
3	Partially correct	29 ms	7624 KB	Partially correct
4	Correct	41 ms	8708 KB	Output is correct
5	Correct	27 ms	7396 KB	Output is correct
6	Correct	32 ms	7640 KB	Output is correct
7	Partially correct	33 ms	7996 KB	Partially correct
8	Partially correct	34 ms	7880 KB	Partially correct
9	Correct	54 ms	8788 KB	Output is correct
10	Partially correct	212 ms	15472 KB	Partially correct
11	Correct	69 ms	10448 KB	Output is correct
12	Partially correct	91 ms	11828 KB	Partially correct
13	Correct	78 ms	10904 KB	Output is correct
14	Correct	76 ms	9884 KB	Output is correct
15	Partially correct	107 ms	11948 KB	Partially correct
16	Correct	110 ms	12288 KB	Output is correct
17	Partially correct	83 ms	11556 KB	Partially correct
18	Correct	86 ms	11456 KB	Output is correct
19	Partially correct	126 ms	14012 KB	Partially correct
20	Correct	213 ms	17604 KB	Output is correct
21	Correct	130 ms	14548 KB	Output is correct
22	Partially correct	115 ms	13336 KB	Partially correct
23	Correct	165 ms	14424 KB	Output is correct
24	Partially correct	143 ms	14380 KB	Partially correct
25	Correct	115 ms	13868 KB	Output is correct
26	Correct	108 ms	13384 KB	Output is correct
27	Partially correct	131 ms	14516 KB	Partially correct
28	Partially correct	132 ms	14528 KB	Partially correct
29	Partially correct	165 ms	16300 KB	Partially correct
30	Correct	254 ms	18268 KB	Output is correct
31	Correct	148 ms	16020 KB	Output is correct
32	Partially correct	126 ms	14464 KB	Partially correct
33	Correct	130 ms	14844 KB	Output is correct
34	Correct	149 ms	15332 KB	Output is correct
35	Correct	140 ms	14928 KB	Output is correct
36	Correct	135 ms	15300 KB	Output is correct
37	Correct	156 ms	16684 KB	Output is correct
38	Partially correct	198 ms	16340 KB	Partially correct
39	Partially correct	165 ms	16376 KB	Partially correct
40	Correct	232 ms	18824 KB	Output is correct
41	Partially correct	329 ms	21180 KB	Partially correct