Submission #733609

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
733609	2023-05-01T04:46:46 Z	SanguineChameleon	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	77 ms	115212 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 = 2e6 + 20;
const int inf = 1e9 + 20;
int B[maxN];
int P[maxN];
vector<int> adj0[maxN];
vector<int> adj1[maxC];
int dist[maxC];
int pos[maxC];
bool flag[maxN];
int id[maxN];

void just_do_it() {
	fill_n(pos, maxC, -1);
	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) {
					adj1[cnt].emplace_back(cnt + 1);
					adj1[cnt + 1].emplace_back(cnt);
				}
				if (cur == B[i]) {
					adj0[B[i]].emplace_back(cnt);
				}
				pos[cnt] = cur;
				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) {
					adj1[cnt].emplace_back(cnt + 1);
					adj1[cnt + 1].emplace_back(cnt);
				}
				id[cur] = cnt;
				pos[cnt] = cur;
				cnt++;
			}
		}
		for (int i = 0; i < M; i++) {
			if (P[i] == d && !flag[B[i]]) {
				flag[B[i]] = true;
				adj0[B[i]].emplace_back(id[B[i]]);
			}
		}
	}
	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();
		if (u == B[1]) {
			cout << dist[u];
			return;
		}
		q.pop_front();
		for (auto v: adj0[u]) {
			if (dist[u] < dist[v]) {
				dist[v] = dist[u];
				q.push_front(v);
			}
		}
		if (pos[u] != -1) {
			int v = pos[u];
			if (dist[u] < dist[v]) {
				dist[v] = dist[u];
				q.push_front(v);
			}
		}
		for (auto v: adj1[u]) {
			if (dist[u] + 1 < dist[v]) {
				dist[v] = dist[u] + 1;
				q.push_back(v);
			}
		}
	}
	cout << -1;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	55728 KB	Output is correct
2	Correct	26 ms	55720 KB	Output is correct
3	Correct	28 ms	55836 KB	Output is correct
4	Correct	26 ms	55760 KB	Output is correct
5	Correct	28 ms	55820 KB	Output is correct
6	Correct	27 ms	55740 KB	Output is correct
7	Correct	27 ms	55764 KB	Output is correct

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	55704 KB	Output is correct
2	Correct	30 ms	55736 KB	Output is correct
3	Correct	26 ms	55844 KB	Output is correct
4	Correct	27 ms	55756 KB	Output is correct
5	Correct	34 ms	55752 KB	Output is correct
6	Correct	29 ms	55776 KB	Output is correct
7	Correct	28 ms	55732 KB	Output is correct
8	Correct	31 ms	55832 KB	Output is correct
9	Correct	28 ms	55772 KB	Output is correct
10	Correct	28 ms	55900 KB	Output is correct
11	Correct	28 ms	56048 KB	Output is correct
12	Correct	27 ms	55764 KB	Output is correct
13	Correct	27 ms	55852 KB	Output is correct
14	Correct	28 ms	56080 KB	Output is correct
15	Correct	28 ms	56080 KB	Output is correct

Subtask #3

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	55808 KB	Output is correct
2	Correct	28 ms	55720 KB	Output is correct
3	Correct	28 ms	55752 KB	Output is correct
4	Correct	27 ms	55844 KB	Output is correct
5	Correct	28 ms	55732 KB	Output is correct
6	Correct	27 ms	55784 KB	Output is correct
7	Correct	26 ms	55812 KB	Output is correct
8	Correct	29 ms	55764 KB	Output is correct
9	Correct	31 ms	55804 KB	Output is correct
10	Correct	29 ms	55904 KB	Output is correct
11	Correct	28 ms	56008 KB	Output is correct
12	Correct	28 ms	55824 KB	Output is correct
13	Correct	27 ms	55764 KB	Output is correct
14	Correct	27 ms	56020 KB	Output is correct
15	Correct	28 ms	56100 KB	Output is correct
16	Correct	28 ms	55988 KB	Output is correct
17	Correct	32 ms	56788 KB	Output is correct
18	Correct	33 ms	57132 KB	Output is correct
19	Correct	28 ms	56584 KB	Output is correct
20	Correct	27 ms	55956 KB	Output is correct
21	Correct	29 ms	55988 KB	Output is correct
22	Correct	29 ms	56548 KB	Output is correct
23	Runtime error	76 ms	115196 KB	Execution killed with signal 11
24	Halted	0 ms	0 KB	-

Subtask #4

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	55764 KB	Output is correct
2	Correct	26 ms	55808 KB	Output is correct
3	Correct	28 ms	55760 KB	Output is correct
4	Correct	28 ms	55764 KB	Output is correct
5	Correct	27 ms	55732 KB	Output is correct
6	Correct	27 ms	55844 KB	Output is correct
7	Correct	27 ms	55764 KB	Output is correct
8	Correct	30 ms	55728 KB	Output is correct
9	Correct	26 ms	55768 KB	Output is correct
10	Correct	28 ms	55828 KB	Output is correct
11	Correct	29 ms	56036 KB	Output is correct
12	Correct	30 ms	55884 KB	Output is correct
13	Correct	34 ms	55740 KB	Output is correct
14	Correct	28 ms	56104 KB	Output is correct
15	Correct	28 ms	56020 KB	Output is correct
16	Correct	28 ms	55912 KB	Output is correct
17	Correct	30 ms	56840 KB	Output is correct
18	Correct	30 ms	57068 KB	Output is correct
19	Correct	30 ms	56584 KB	Output is correct
20	Correct	31 ms	56100 KB	Output is correct
21	Correct	34 ms	55944 KB	Output is correct
22	Correct	30 ms	56524 KB	Output is correct
23	Runtime error	74 ms	115152 KB	Execution killed with signal 11
24	Halted	0 ms	0 KB	-

Subtask #5

0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	55824 KB	Output is correct
2	Correct	27 ms	55752 KB	Output is correct
3	Correct	28 ms	55764 KB	Output is correct
4	Correct	32 ms	55764 KB	Output is correct
5	Correct	28 ms	55784 KB	Output is correct
6	Correct	27 ms	55764 KB	Output is correct
7	Correct	30 ms	55908 KB	Output is correct
8	Correct	27 ms	55724 KB	Output is correct
9	Correct	33 ms	55816 KB	Output is correct
10	Correct	30 ms	55892 KB	Output is correct
11	Correct	29 ms	56012 KB	Output is correct
12	Correct	27 ms	55788 KB	Output is correct
13	Correct	28 ms	55744 KB	Output is correct
14	Correct	29 ms	55968 KB	Output is correct
15	Correct	29 ms	56084 KB	Output is correct
16	Correct	30 ms	55924 KB	Output is correct
17	Correct	32 ms	56908 KB	Output is correct
18	Correct	31 ms	57144 KB	Output is correct
19	Correct	33 ms	56604 KB	Output is correct
20	Correct	31 ms	56004 KB	Output is correct
21	Correct	31 ms	55996 KB	Output is correct
22	Correct	30 ms	56572 KB	Output is correct
23	Runtime error	77 ms	115212 KB	Execution killed with signal 11
24	Halted	0 ms	0 KB	-