oj.uz

Submission #733601

# Submission time Handle Problem Language Result Execution time Memory
733601 2023-05-01T04:34:33 Z SanguineChameleon Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 345 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;
		}
		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 58 ms 117736 KB Output is correct
2 Correct 62 ms 117676 KB Output is correct
3 Correct 56 ms 117736 KB Output is correct
4 Correct 59 ms 117792 KB Output is correct
5 Correct 59 ms 117636 KB Output is correct
6 Correct 57 ms 117720 KB Output is correct
7 Correct 64 ms 117700 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 117668 KB Output is correct
2 Correct 55 ms 117732 KB Output is correct
3 Correct 59 ms 117688 KB Output is correct
4 Correct 54 ms 117648 KB Output is correct
5 Correct 58 ms 117720 KB Output is correct
6 Correct 57 ms 117708 KB Output is correct
7 Correct 56 ms 117716 KB Output is correct
8 Correct 58 ms 117648 KB Output is correct
9 Correct 59 ms 117808 KB Output is correct
10 Correct 56 ms 117784 KB Output is correct
11 Correct 56 ms 117900 KB Output is correct
12 Correct 57 ms 117772 KB Output is correct
13 Correct 57 ms 117688 KB Output is correct
14 Correct 58 ms 117964 KB Output is correct
15 Correct 58 ms 117964 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 117652 KB Output is correct
2 Correct 55 ms 117696 KB Output is correct
3 Correct 57 ms 117632 KB Output is correct
4 Correct 57 ms 117736 KB Output is correct
5 Correct 55 ms 117740 KB Output is correct
6 Correct 56 ms 117740 KB Output is correct
7 Correct 57 ms 117708 KB Output is correct
8 Correct 58 ms 117724 KB Output is correct
9 Correct 57 ms 117664 KB Output is correct
10 Correct 58 ms 117756 KB Output is correct
11 Correct 57 ms 118028 KB Output is correct
12 Correct 56 ms 117796 KB Output is correct
13 Correct 58 ms 117788 KB Output is correct
14 Correct 57 ms 118048 KB Output is correct
15 Correct 57 ms 117964 KB Output is correct
16 Correct 60 ms 117944 KB Output is correct
17 Correct 61 ms 119104 KB Output is correct
18 Correct 65 ms 121528 KB Output is correct
19 Correct 65 ms 122224 KB Output is correct
20 Correct 67 ms 122220 KB Output is correct
21 Correct 60 ms 118140 KB Output is correct
22 Correct 68 ms 121584 KB Output is correct
23 Correct 64 ms 121028 KB Output is correct
24 Correct 67 ms 122180 KB Output is correct
25 Correct 67 ms 122412 KB Output is correct
26 Correct 70 ms 122380 KB Output is correct
27 Correct 68 ms 122172 KB Output is correct
28 Correct 71 ms 122644 KB Output is correct
29 Correct 69 ms 122140 KB Output is correct
30 Correct 68 ms 122128 KB Output is correct
31 Correct 67 ms 122324 KB Output is correct
32 Correct 69 ms 122748 KB Output is correct
33 Correct 76 ms 124108 KB Output is correct
34 Correct 78 ms 124268 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 117736 KB Output is correct
2 Correct 56 ms 117732 KB Output is correct
3 Correct 56 ms 117716 KB Output is correct
4 Correct 58 ms 117736 KB Output is correct
5 Correct 61 ms 117724 KB Output is correct
6 Correct 57 ms 117676 KB Output is correct
7 Correct 60 ms 117708 KB Output is correct
8 Correct 57 ms 117652 KB Output is correct
9 Correct 58 ms 117760 KB Output is correct
10 Correct 58 ms 117804 KB Output is correct
11 Correct 58 ms 117964 KB Output is correct
12 Correct 57 ms 117740 KB Output is correct
13 Correct 58 ms 117708 KB Output is correct
14 Correct 58 ms 118048 KB Output is correct
15 Correct 58 ms 117988 KB Output is correct
16 Correct 57 ms 117996 KB Output is correct
17 Correct 59 ms 119140 KB Output is correct
18 Correct 66 ms 121500 KB Output is correct
19 Correct 66 ms 122216 KB Output is correct
20 Correct 68 ms 122176 KB Output is correct
21 Correct 61 ms 118204 KB Output is correct
22 Correct 67 ms 121640 KB Output is correct
23 Correct 72 ms 120984 KB Output is correct
24 Correct 68 ms 122176 KB Output is correct
25 Correct 67 ms 122324 KB Output is correct
26 Correct 71 ms 122376 KB Output is correct
27 Correct 68 ms 122180 KB Output is correct
28 Correct 68 ms 122656 KB Output is correct
29 Correct 70 ms 122180 KB Output is correct
30 Correct 67 ms 122204 KB Output is correct
31 Correct 70 ms 122308 KB Output is correct
32 Correct 68 ms 122700 KB Output is correct
33 Correct 76 ms 124076 KB Output is correct
34 Correct 76 ms 124168 KB Output is correct
35 Correct 87 ms 124144 KB Output is correct
36 Correct 65 ms 120104 KB Output is correct
37 Correct 99 ms 128460 KB Output is correct
38 Correct 110 ms 128028 KB Output is correct
39 Correct 110 ms 127960 KB Output is correct
40 Correct 104 ms 128220 KB Output is correct
41 Correct 101 ms 128096 KB Output is correct
42 Correct 70 ms 122572 KB Output is correct
43 Correct 71 ms 122448 KB Output is correct
44 Correct 78 ms 122496 KB Output is correct
45 Correct 191 ms 142308 KB Output is correct
46 Correct 189 ms 142268 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 117668 KB Output is correct
2 Correct 58 ms 117696 KB Output is correct
3 Correct 58 ms 117708 KB Output is correct
4 Correct 57 ms 117744 KB Output is correct
5 Correct 61 ms 117688 KB Output is correct
6 Correct 67 ms 117736 KB Output is correct
7 Correct 62 ms 117704 KB Output is correct
8 Correct 57 ms 117676 KB Output is correct
9 Correct 57 ms 117756 KB Output is correct
10 Correct 57 ms 117812 KB Output is correct
11 Correct 59 ms 118004 KB Output is correct
12 Correct 57 ms 117684 KB Output is correct
13 Correct 58 ms 117732 KB Output is correct
14 Correct 59 ms 118052 KB Output is correct
15 Correct 59 ms 118048 KB Output is correct
16 Correct 57 ms 117964 KB Output is correct
17 Correct 62 ms 119116 KB Output is correct
18 Correct 72 ms 121572 KB Output is correct
19 Correct 70 ms 122316 KB Output is correct
20 Correct 67 ms 122172 KB Output is correct
21 Correct 59 ms 118124 KB Output is correct
22 Correct 66 ms 121576 KB Output is correct
23 Correct 64 ms 121080 KB Output is correct
24 Correct 73 ms 122216 KB Output is correct
25 Correct 68 ms 122284 KB Output is correct
26 Correct 69 ms 122260 KB Output is correct
27 Correct 67 ms 122208 KB Output is correct
28 Correct 69 ms 122644 KB Output is correct
29 Correct 69 ms 122160 KB Output is correct
30 Correct 72 ms 122136 KB Output is correct
31 Correct 72 ms 122288 KB Output is correct
32 Correct 75 ms 122796 KB Output is correct
33 Correct 81 ms 124208 KB Output is correct
34 Correct 76 ms 124144 KB Output is correct
35 Correct 82 ms 124192 KB Output is correct
36 Correct 68 ms 120268 KB Output is correct
37 Correct 106 ms 128284 KB Output is correct
38 Correct 103 ms 127940 KB Output is correct
39 Correct 101 ms 128008 KB Output is correct
40 Correct 101 ms 128028 KB Output is correct
41 Correct 101 ms 128076 KB Output is correct
42 Correct 82 ms 122588 KB Output is correct
43 Correct 73 ms 122504 KB Output is correct
44 Correct 77 ms 122428 KB Output is correct
45 Correct 192 ms 142280 KB Output is correct
46 Correct 199 ms 142320 KB Output is correct
47 Correct 345 ms 207020 KB Output is correct
48 Runtime error 333 ms 262144 KB Execution killed with signal 9
49 Halted 0 ms 0 KB -