oj.uz

Submission #454809

# Submission time Handle Problem Language Result Execution time Memory
454809 2021-08-05T08:29:27 Z kingfran1907 007 (CEOI14_007) C++14
10 / 100
 285 ms 16144 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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