Submission #733600

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
733600	2023-05-01T04:34:02 Z	SanguineChameleon	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	170 ms	142140 KB

skyscraper

#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 = 1e6 + 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	13 ms	23744 KB	Output is correct
2	Correct	13 ms	23792 KB	Output is correct
3	Correct	13 ms	23764 KB	Output is correct
4	Correct	12 ms	23764 KB	Output is correct
5	Correct	14 ms	23764 KB	Output is correct
6	Correct	14 ms	23804 KB	Output is correct
7	Correct	13 ms	23764 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23764 KB	Output is correct
2	Correct	12 ms	23768 KB	Output is correct
3	Correct	13 ms	23832 KB	Output is correct
4	Correct	12 ms	23720 KB	Output is correct
5	Correct	12 ms	23764 KB	Output is correct
6	Correct	12 ms	23776 KB	Output is correct
7	Correct	13 ms	23764 KB	Output is correct
8	Correct	13 ms	23764 KB	Output is correct
9	Correct	13 ms	23760 KB	Output is correct
10	Correct	15 ms	23892 KB	Output is correct
11	Correct	13 ms	24020 KB	Output is correct
12	Correct	13 ms	23892 KB	Output is correct
13	Correct	15 ms	23840 KB	Output is correct
14	Correct	13 ms	24020 KB	Output is correct
15	Correct	14 ms	24112 KB	Output is correct

Subtask #3
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	23764 KB	Output is correct
2	Correct	12 ms	23764 KB	Output is correct
3	Correct	13 ms	23772 KB	Output is correct
4	Correct	14 ms	23764 KB	Output is correct
5	Correct	12 ms	23764 KB	Output is correct
6	Correct	12 ms	23816 KB	Output is correct
7	Correct	12 ms	23764 KB	Output is correct
8	Correct	13 ms	23764 KB	Output is correct
9	Correct	13 ms	23828 KB	Output is correct
10	Correct	14 ms	23892 KB	Output is correct
11	Correct	14 ms	24020 KB	Output is correct
12	Correct	13 ms	23844 KB	Output is correct
13	Correct	12 ms	23892 KB	Output is correct
14	Correct	13 ms	24020 KB	Output is correct
15	Correct	14 ms	24124 KB	Output is correct
16	Correct	14 ms	24020 KB	Output is correct
17	Correct	17 ms	25192 KB	Output is correct
18	Correct	22 ms	27668 KB	Output is correct
19	Correct	25 ms	28412 KB	Output is correct
20	Correct	28 ms	28276 KB	Output is correct
21	Correct	15 ms	24200 KB	Output is correct
22	Correct	22 ms	27692 KB	Output is correct
23	Correct	24 ms	27092 KB	Output is correct
24	Correct	28 ms	28360 KB	Output is correct
25	Correct	30 ms	28496 KB	Output is correct
26	Correct	23 ms	28372 KB	Output is correct
27	Correct	23 ms	28364 KB	Output is correct
28	Correct	27 ms	28804 KB	Output is correct
29	Correct	26 ms	28244 KB	Output is correct
30	Correct	24 ms	28176 KB	Output is correct
31	Correct	24 ms	28344 KB	Output is correct
32	Correct	25 ms	28816 KB	Output is correct
33	Correct	35 ms	30280 KB	Output is correct
34	Correct	36 ms	30224 KB	Output is correct

Subtask #4
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23800 KB	Output is correct
2	Correct	12 ms	23764 KB	Output is correct
3	Correct	12 ms	23764 KB	Output is correct
4	Correct	13 ms	23776 KB	Output is correct
5	Correct	13 ms	23820 KB	Output is correct
6	Correct	13 ms	23764 KB	Output is correct
7	Correct	13 ms	23788 KB	Output is correct
8	Correct	13 ms	23776 KB	Output is correct
9	Correct	15 ms	23780 KB	Output is correct
10	Correct	13 ms	23892 KB	Output is correct
11	Correct	14 ms	24020 KB	Output is correct
12	Correct	13 ms	23892 KB	Output is correct
13	Correct	13 ms	23892 KB	Output is correct
14	Correct	13 ms	24040 KB	Output is correct
15	Correct	13 ms	24020 KB	Output is correct
16	Correct	15 ms	24020 KB	Output is correct
17	Correct	17 ms	25136 KB	Output is correct
18	Correct	21 ms	27604 KB	Output is correct
19	Correct	22 ms	28364 KB	Output is correct
20	Correct	24 ms	28284 KB	Output is correct
21	Correct	15 ms	24276 KB	Output is correct
22	Correct	22 ms	27724 KB	Output is correct
23	Correct	21 ms	27096 KB	Output is correct
24	Correct	26 ms	28284 KB	Output is correct
25	Correct	24 ms	28500 KB	Output is correct
26	Correct	24 ms	28440 KB	Output is correct
27	Correct	23 ms	28384 KB	Output is correct
28	Correct	24 ms	28720 KB	Output is correct
29	Correct	26 ms	28244 KB	Output is correct
30	Correct	23 ms	28284 KB	Output is correct
31	Correct	24 ms	28300 KB	Output is correct
32	Correct	25 ms	28884 KB	Output is correct
33	Correct	32 ms	30260 KB	Output is correct
34	Correct	35 ms	30304 KB	Output is correct
35	Correct	41 ms	30404 KB	Output is correct
36	Correct	21 ms	26232 KB	Output is correct
37	Correct	65 ms	34608 KB	Output is correct
38	Correct	68 ms	34344 KB	Output is correct
39	Correct	60 ms	34368 KB	Output is correct
40	Correct	61 ms	34340 KB	Output is correct
41	Correct	62 ms	34444 KB	Output is correct
42	Correct	29 ms	28784 KB	Output is correct
43	Correct	28 ms	28788 KB	Output is correct
44	Correct	28 ms	28756 KB	Output is correct
45	Correct	126 ms	48588 KB	Output is correct
46	Correct	134 ms	48604 KB	Output is correct

Subtask #5
0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	23764 KB	Output is correct
2	Correct	14 ms	23716 KB	Output is correct
3	Correct	13 ms	23712 KB	Output is correct
4	Correct	13 ms	23764 KB	Output is correct
5	Correct	14 ms	23776 KB	Output is correct
6	Correct	13 ms	23816 KB	Output is correct
7	Correct	12 ms	23796 KB	Output is correct
8	Correct	12 ms	23768 KB	Output is correct
9	Correct	12 ms	23764 KB	Output is correct
10	Correct	13 ms	23816 KB	Output is correct
11	Correct	13 ms	24020 KB	Output is correct
12	Correct	13 ms	23892 KB	Output is correct
13	Correct	14 ms	23796 KB	Output is correct
14	Correct	14 ms	24132 KB	Output is correct
15	Correct	14 ms	24148 KB	Output is correct
16	Correct	14 ms	24020 KB	Output is correct
17	Correct	18 ms	25172 KB	Output is correct
18	Correct	22 ms	27604 KB	Output is correct
19	Correct	23 ms	28376 KB	Output is correct
20	Correct	25 ms	28372 KB	Output is correct
21	Correct	14 ms	24212 KB	Output is correct
22	Correct	22 ms	27696 KB	Output is correct
23	Correct	20 ms	27088 KB	Output is correct
24	Correct	24 ms	28296 KB	Output is correct
25	Correct	23 ms	28500 KB	Output is correct
26	Correct	23 ms	28412 KB	Output is correct
27	Correct	23 ms	28372 KB	Output is correct
28	Correct	24 ms	28824 KB	Output is correct
29	Correct	25 ms	28368 KB	Output is correct
30	Correct	23 ms	28244 KB	Output is correct
31	Correct	25 ms	28304 KB	Output is correct
32	Correct	26 ms	28840 KB	Output is correct
33	Correct	32 ms	30172 KB	Output is correct
34	Correct	33 ms	30232 KB	Output is correct
35	Correct	40 ms	30480 KB	Output is correct
36	Correct	20 ms	26264 KB	Output is correct
37	Correct	59 ms	34528 KB	Output is correct
38	Correct	59 ms	34308 KB	Output is correct
39	Correct	59 ms	34376 KB	Output is correct
40	Correct	58 ms	34480 KB	Output is correct
41	Correct	57 ms	34360 KB	Output is correct
42	Correct	27 ms	28884 KB	Output is correct
43	Correct	26 ms	28756 KB	Output is correct
44	Correct	26 ms	28752 KB	Output is correct
45	Correct	153 ms	48540 KB	Output is correct
46	Correct	149 ms	48484 KB	Output is correct
47	Runtime error	170 ms	142140 KB	Execution killed with signal 11
48	Halted	0 ms	0 KB	-

Submission #733600

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 14.0 / 14.0

Subtask #4 21.0 / 21.0

Subtask #5 0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
14.0 / 14.0

Subtask #4
21.0 / 21.0

Subtask #5
0 / 43.0