oj.uz

Submission #733602

# Submission time Handle Problem Language Result Execution time Memory
733602 2023-05-01T04:37:26 Z SanguineChameleon Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 350 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 = 5e6 + 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 55 ms 117732 KB Output is correct
2 Correct 55 ms 117720 KB Output is correct
3 Correct 55 ms 117620 KB Output is correct
4 Correct 58 ms 117708 KB Output is correct
5 Correct 56 ms 117736 KB Output is correct
6 Correct 55 ms 117676 KB Output is correct
7 Correct 57 ms 117728 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 117636 KB Output is correct
2 Correct 54 ms 117696 KB Output is correct
3 Correct 63 ms 117628 KB Output is correct
4 Correct 56 ms 117740 KB Output is correct
5 Correct 56 ms 117828 KB Output is correct
6 Correct 59 ms 117736 KB Output is correct
7 Correct 56 ms 117788 KB Output is correct
8 Correct 55 ms 117732 KB Output is correct
9 Correct 59 ms 117704 KB Output is correct
10 Correct 57 ms 117836 KB Output is correct
11 Correct 55 ms 117988 KB Output is correct
12 Correct 57 ms 117788 KB Output is correct
13 Correct 61 ms 117768 KB Output is correct
14 Correct 58 ms 118044 KB Output is correct
15 Correct 57 ms 117992 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 117620 KB Output is correct
2 Correct 59 ms 117612 KB Output is correct
3 Correct 55 ms 117708 KB Output is correct
4 Correct 57 ms 117612 KB Output is correct
5 Correct 59 ms 117684 KB Output is correct
6 Correct 55 ms 117656 KB Output is correct
7 Correct 55 ms 117736 KB Output is correct
8 Correct 55 ms 117728 KB Output is correct
9 Correct 57 ms 117688 KB Output is correct
10 Correct 56 ms 117748 KB Output is correct
11 Correct 57 ms 117932 KB Output is correct
12 Correct 55 ms 117784 KB Output is correct
13 Correct 54 ms 117764 KB Output is correct
14 Correct 57 ms 118044 KB Output is correct
15 Correct 58 ms 117964 KB Output is correct
16 Correct 60 ms 117892 KB Output is correct
17 Correct 59 ms 119132 KB Output is correct
18 Correct 64 ms 119624 KB Output is correct
19 Correct 59 ms 118920 KB Output is correct
20 Correct 60 ms 117828 KB Output is correct
21 Correct 56 ms 117968 KB Output is correct
22 Correct 59 ms 118816 KB Output is correct
23 Correct 60 ms 119312 KB Output is correct
24 Correct 63 ms 120784 KB Output is correct
25 Correct 58 ms 118212 KB Output is correct
26 Correct 61 ms 120252 KB Output is correct
27 Correct 60 ms 119244 KB Output is correct
28 Correct 63 ms 121416 KB Output is correct
29 Correct 66 ms 121024 KB Output is correct
30 Correct 58 ms 118640 KB Output is correct
31 Correct 62 ms 119408 KB Output is correct
32 Correct 60 ms 118904 KB Output is correct
33 Correct 77 ms 124196 KB Output is correct
34 Correct 76 ms 124144 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 117732 KB Output is correct
2 Correct 56 ms 117720 KB Output is correct
3 Correct 58 ms 117636 KB Output is correct
4 Correct 56 ms 117624 KB Output is correct
5 Correct 56 ms 117616 KB Output is correct
6 Correct 56 ms 117736 KB Output is correct
7 Correct 55 ms 117664 KB Output is correct
8 Correct 58 ms 117740 KB Output is correct
9 Correct 62 ms 117708 KB Output is correct
10 Correct 61 ms 117780 KB Output is correct
11 Correct 57 ms 117976 KB Output is correct
12 Correct 55 ms 117708 KB Output is correct
13 Correct 64 ms 117732 KB Output is correct
14 Correct 57 ms 118000 KB Output is correct
15 Correct 59 ms 117964 KB Output is correct
16 Correct 56 ms 117988 KB Output is correct
17 Correct 60 ms 119116 KB Output is correct
18 Correct 59 ms 119536 KB Output is correct
19 Correct 58 ms 118872 KB Output is correct
20 Correct 56 ms 117928 KB Output is correct
21 Correct 58 ms 117956 KB Output is correct
22 Correct 59 ms 118864 KB Output is correct
23 Correct 61 ms 119244 KB Output is correct
24 Correct 63 ms 120744 KB Output is correct
25 Correct 65 ms 118252 KB Output is correct
26 Correct 64 ms 120204 KB Output is correct
27 Correct 60 ms 119244 KB Output is correct
28 Correct 65 ms 121412 KB Output is correct
29 Correct 63 ms 120996 KB Output is correct
30 Correct 60 ms 118596 KB Output is correct
31 Correct 60 ms 119468 KB Output is correct
32 Correct 59 ms 118940 KB Output is correct
33 Correct 75 ms 124172 KB Output is correct
34 Correct 75 ms 124088 KB Output is correct
35 Correct 79 ms 124160 KB Output is correct
36 Correct 63 ms 119932 KB Output is correct
37 Correct 101 ms 128372 KB Output is correct
38 Correct 97 ms 128032 KB Output is correct
39 Correct 100 ms 127964 KB Output is correct
40 Correct 99 ms 128060 KB Output is correct
41 Correct 99 ms 128076 KB Output is correct
42 Correct 68 ms 120524 KB Output is correct
43 Correct 62 ms 119544 KB Output is correct
44 Correct 60 ms 118088 KB Output is correct
45 Correct 159 ms 142360 KB Output is correct
46 Correct 193 ms 142252 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 117620 KB Output is correct
2 Correct 56 ms 117616 KB Output is correct
3 Correct 64 ms 117628 KB Output is correct
4 Correct 56 ms 117720 KB Output is correct
5 Correct 56 ms 117736 KB Output is correct
6 Correct 56 ms 117804 KB Output is correct
7 Correct 60 ms 117732 KB Output is correct
8 Correct 57 ms 117624 KB Output is correct
9 Correct 63 ms 117708 KB Output is correct
10 Correct 57 ms 117836 KB Output is correct
11 Correct 57 ms 118092 KB Output is correct
12 Correct 57 ms 117776 KB Output is correct
13 Correct 60 ms 117728 KB Output is correct
14 Correct 59 ms 117960 KB Output is correct
15 Correct 58 ms 117964 KB Output is correct
16 Correct 57 ms 117952 KB Output is correct
17 Correct 61 ms 119016 KB Output is correct
18 Correct 62 ms 119624 KB Output is correct
19 Correct 67 ms 118880 KB Output is correct
20 Correct 57 ms 117936 KB Output is correct
21 Correct 57 ms 117868 KB Output is correct
22 Correct 58 ms 118824 KB Output is correct
23 Correct 59 ms 119224 KB Output is correct
24 Correct 65 ms 120824 KB Output is correct
25 Correct 58 ms 118240 KB Output is correct
26 Correct 65 ms 120196 KB Output is correct
27 Correct 63 ms 119328 KB Output is correct
28 Correct 66 ms 121420 KB Output is correct
29 Correct 93 ms 120956 KB Output is correct
30 Correct 58 ms 118604 KB Output is correct
31 Correct 65 ms 119400 KB Output is correct
32 Correct 59 ms 118860 KB Output is correct
33 Correct 77 ms 124232 KB Output is correct
34 Correct 75 ms 124136 KB Output is correct
35 Correct 84 ms 124132 KB Output is correct
36 Correct 63 ms 119884 KB Output is correct
37 Correct 105 ms 128472 KB Output is correct
38 Correct 116 ms 127948 KB Output is correct
39 Correct 99 ms 127952 KB Output is correct
40 Correct 101 ms 128104 KB Output is correct
41 Correct 100 ms 128040 KB Output is correct
42 Correct 65 ms 120516 KB Output is correct
43 Correct 64 ms 119500 KB Output is correct
44 Correct 64 ms 118024 KB Output is correct
45 Correct 191 ms 142268 KB Output is correct
46 Correct 191 ms 142284 KB Output is correct
47 Correct 350 ms 207148 KB Output is correct
48 Correct 308 ms 234700 KB Output is correct
49 Correct 262 ms 212024 KB Output is correct
50 Correct 264 ms 214396 KB Output is correct
51 Runtime error 348 ms 262144 KB Execution killed with signal 9
52 Halted 0 ms 0 KB -