oj.uz

Submission #733603

# Submission time Handle Problem Language Result Execution time Memory
733603 2023-05-01T04:38:53 Z SanguineChameleon Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 336 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int maxN = 3e4 + 20;
const int maxC = 2e6 + 20;
const int inf = 1e9 + 20;
int B[maxN];
int P[maxN];
vector<pair<int, bool>> adj[maxC];
int dist[maxC];
bool flag[maxN];
int id[maxN];

void just_do_it() {
	int N, M;
	cin >> N >> M;
	const int lim = sqrt(N);
	int cnt = N;
	for (int i = 0; i < M; i++) {
		cin >> B[i] >> P[i];
		if (P[i] > lim) {
			int cur = B[i] % P[i];
			int nxt = cur + P[i];
			for (; cur < N; cur += P[i], nxt += P[i]) {
				if (nxt < N) {
					adj[cnt].emplace_back(cnt + 1, 1);
					adj[cnt + 1].emplace_back(cnt, 1);
				}
				if (cur == B[i]) {
					adj[B[i]].emplace_back(cnt, 0);
				}
				adj[cnt].emplace_back(cur, 0);
				cnt++;
			}
		}
	}
	for (int d = 1; d <= lim; d++) {
		for (int i = 0; i < N; i++) {
			flag[i] = false;
		}
		bool found = false;
		for (int i = 0; i < M; i++) {
			if (P[i] == d) {
				found = true;
				break;
			}
		}
		if (!found) {
			continue;
		}
		for (int i = 0; i < d; i++) {
			int cur = i;
			int nxt = cur + d;
			for (; cur < N; cur += d, nxt += d) {
				if (nxt < N) {
					adj[cnt].emplace_back(cnt + 1, 1);
					adj[cnt + 1].emplace_back(cnt, 1);
				}
				id[cur] = cnt;
				adj[cnt].emplace_back(cur, 0);
				cnt++;
			}
		}
		for (int i = 0; i < M; i++) {
			if (P[i] == d && !flag[B[i]]) {
				flag[B[i]] = true;
				adj[B[i]].emplace_back(id[B[i]], 0);
			}
		}
	}
	assert(cnt < maxC);
	for (int i = 0; i < cnt; i++) {
		dist[i] = inf;
	}
	dist[B[0]] = 0;
	deque<int> q = {B[0]};
	while (!q.empty()) {
		int u = q.front();
		q.pop_front();
		for (auto p: adj[u]) {
			int v = p.first;
			int w = p.second;
			if (dist[u] + w < dist[v]) {
				dist[v] = dist[u] + w;
				if (w == 0) {
					q.push_front(v);
				}
				else {
					q.push_back(v);
				}
			}
		}
	}
	if (dist[B[1]] == inf) {
		cout << -1;
	}
	else {
		cout << dist[B[1]];
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47316 KB Output is correct
2 Correct 22 ms 47188 KB Output is correct
3 Correct 23 ms 47296 KB Output is correct
4 Correct 24 ms 47228 KB Output is correct
5 Correct 30 ms 47216 KB Output is correct
6 Correct 22 ms 47312 KB Output is correct
7 Correct 22 ms 47188 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 24 ms 47280 KB Output is correct
3 Correct 27 ms 47280 KB Output is correct
4 Correct 24 ms 47296 KB Output is correct
5 Correct 31 ms 47188 KB Output is correct
6 Correct 24 ms 47204 KB Output is correct
7 Correct 24 ms 47280 KB Output is correct
8 Correct 30 ms 47316 KB Output is correct
9 Correct 24 ms 47304 KB Output is correct
10 Correct 24 ms 47380 KB Output is correct
11 Correct 26 ms 47572 KB Output is correct
12 Correct 26 ms 47248 KB Output is correct
13 Correct 28 ms 47248 KB Output is correct
14 Correct 36 ms 47572 KB Output is correct
15 Correct 27 ms 47552 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47260 KB Output is correct
2 Correct 25 ms 47256 KB Output is correct
3 Correct 25 ms 47180 KB Output is correct
4 Correct 25 ms 47188 KB Output is correct
5 Correct 27 ms 47288 KB Output is correct
6 Correct 27 ms 47188 KB Output is correct
7 Correct 23 ms 47304 KB Output is correct
8 Correct 22 ms 47316 KB Output is correct
9 Correct 26 ms 47224 KB Output is correct
10 Correct 27 ms 47340 KB Output is correct
11 Correct 27 ms 47488 KB Output is correct
12 Correct 24 ms 47284 KB Output is correct
13 Correct 24 ms 47300 KB Output is correct
14 Correct 27 ms 47580 KB Output is correct
15 Correct 28 ms 47516 KB Output is correct
16 Correct 27 ms 47472 KB Output is correct
17 Correct 30 ms 48704 KB Output is correct
18 Correct 29 ms 49112 KB Output is correct
19 Correct 35 ms 48324 KB Output is correct
20 Correct 26 ms 47436 KB Output is correct
21 Correct 25 ms 47564 KB Output is correct
22 Correct 26 ms 48448 KB Output is correct
23 Correct 28 ms 48836 KB Output is correct
24 Correct 33 ms 50380 KB Output is correct
25 Correct 27 ms 47720 KB Output is correct
26 Correct 37 ms 49756 KB Output is correct
27 Correct 34 ms 48848 KB Output is correct
28 Correct 34 ms 50892 KB Output is correct
29 Correct 45 ms 50544 KB Output is correct
30 Correct 27 ms 48152 KB Output is correct
31 Correct 28 ms 48980 KB Output is correct
32 Correct 27 ms 48536 KB Output is correct
33 Correct 45 ms 53748 KB Output is correct
34 Correct 45 ms 53716 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47188 KB Output is correct
2 Correct 25 ms 47188 KB Output is correct
3 Correct 24 ms 47204 KB Output is correct
4 Correct 26 ms 47316 KB Output is correct
5 Correct 25 ms 47256 KB Output is correct
6 Correct 26 ms 47188 KB Output is correct
7 Correct 26 ms 47216 KB Output is correct
8 Correct 25 ms 47252 KB Output is correct
9 Correct 26 ms 47316 KB Output is correct
10 Correct 26 ms 47444 KB Output is correct
11 Correct 30 ms 47548 KB Output is correct
12 Correct 26 ms 47316 KB Output is correct
13 Correct 25 ms 47252 KB Output is correct
14 Correct 27 ms 47572 KB Output is correct
15 Correct 26 ms 47564 KB Output is correct
16 Correct 29 ms 47552 KB Output is correct
17 Correct 29 ms 48596 KB Output is correct
18 Correct 28 ms 49108 KB Output is correct
19 Correct 27 ms 48340 KB Output is correct
20 Correct 26 ms 47464 KB Output is correct
21 Correct 26 ms 47536 KB Output is correct
22 Correct 29 ms 48364 KB Output is correct
23 Correct 32 ms 48808 KB Output is correct
24 Correct 35 ms 50340 KB Output is correct
25 Correct 27 ms 47804 KB Output is correct
26 Correct 31 ms 49700 KB Output is correct
27 Correct 30 ms 48844 KB Output is correct
28 Correct 35 ms 50932 KB Output is correct
29 Correct 35 ms 50548 KB Output is correct
30 Correct 27 ms 48192 KB Output is correct
31 Correct 29 ms 48980 KB Output is correct
32 Correct 27 ms 48468 KB Output is correct
33 Correct 43 ms 53708 KB Output is correct
34 Correct 44 ms 53716 KB Output is correct
35 Correct 53 ms 53684 KB Output is correct
36 Correct 32 ms 49400 KB Output is correct
37 Correct 72 ms 57804 KB Output is correct
38 Correct 68 ms 57528 KB Output is correct
39 Correct 74 ms 57488 KB Output is correct
40 Correct 68 ms 57548 KB Output is correct
41 Correct 69 ms 57636 KB Output is correct
42 Correct 36 ms 50024 KB Output is correct
43 Correct 32 ms 49124 KB Output is correct
44 Correct 34 ms 47680 KB Output is correct
45 Correct 161 ms 71876 KB Output is correct
46 Correct 161 ms 71860 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47272 KB Output is correct
2 Correct 24 ms 47384 KB Output is correct
3 Correct 24 ms 47200 KB Output is correct
4 Correct 25 ms 47188 KB Output is correct
5 Correct 27 ms 47248 KB Output is correct
6 Correct 24 ms 47312 KB Output is correct
7 Correct 25 ms 47256 KB Output is correct
8 Correct 25 ms 47220 KB Output is correct
9 Correct 25 ms 47316 KB Output is correct
10 Correct 25 ms 47360 KB Output is correct
11 Correct 28 ms 47552 KB Output is correct
12 Correct 28 ms 47312 KB Output is correct
13 Correct 25 ms 47268 KB Output is correct
14 Correct 26 ms 47532 KB Output is correct
15 Correct 31 ms 47564 KB Output is correct
16 Correct 26 ms 47488 KB Output is correct
17 Correct 31 ms 48612 KB Output is correct
18 Correct 28 ms 49076 KB Output is correct
19 Correct 27 ms 48372 KB Output is correct
20 Correct 25 ms 47440 KB Output is correct
21 Correct 25 ms 47544 KB Output is correct
22 Correct 27 ms 48404 KB Output is correct
23 Correct 28 ms 48816 KB Output is correct
24 Correct 33 ms 50384 KB Output is correct
25 Correct 26 ms 47840 KB Output is correct
26 Correct 31 ms 49796 KB Output is correct
27 Correct 28 ms 48836 KB Output is correct
28 Correct 33 ms 50900 KB Output is correct
29 Correct 34 ms 50508 KB Output is correct
30 Correct 29 ms 48212 KB Output is correct
31 Correct 29 ms 48956 KB Output is correct
32 Correct 28 ms 48468 KB Output is correct
33 Correct 45 ms 53700 KB Output is correct
34 Correct 45 ms 53716 KB Output is correct
35 Correct 52 ms 53760 KB Output is correct
36 Correct 31 ms 49468 KB Output is correct
37 Correct 74 ms 57876 KB Output is correct
38 Correct 67 ms 57584 KB Output is correct
39 Correct 69 ms 57516 KB Output is correct
40 Correct 68 ms 57652 KB Output is correct
41 Correct 67 ms 57548 KB Output is correct
42 Correct 35 ms 49936 KB Output is correct
43 Correct 32 ms 49128 KB Output is correct
44 Correct 29 ms 47700 KB Output is correct
45 Correct 161 ms 71760 KB Output is correct
46 Correct 163 ms 71860 KB Output is correct
47 Correct 304 ms 136480 KB Output is correct
48 Runtime error 336 ms 262144 KB Execution killed with signal 11
49 Halted 0 ms 0 KB -