oj.uz

Submission #733607

# Submission time Handle Problem Language Result Execution time Memory
733607 2023-05-01T04:42:27 Z SanguineChameleon Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 481 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<int> adj0[maxC];
vector<int> adj1[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) {
					adj1[cnt].emplace_back(cnt + 1);
					adj1[cnt + 1].emplace_back(cnt);
				}
				if (cur == B[i]) {
					adj0[B[i]].emplace_back(cnt);
				}
				adj0[cnt].emplace_back(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;
				adj0[cnt].emplace_back(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();
		q.pop_front();
		for (auto v: adj0[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);
			}
		}
	}
	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 56 ms 94152 KB Output is correct
2 Correct 52 ms 94252 KB Output is correct
3 Correct 45 ms 94200 KB Output is correct
4 Correct 43 ms 94252 KB Output is correct
5 Correct 45 ms 94132 KB Output is correct
6 Correct 44 ms 94156 KB Output is correct
7 Correct 45 ms 94152 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94252 KB Output is correct
2 Correct 48 ms 94272 KB Output is correct
3 Correct 46 ms 94256 KB Output is correct
4 Correct 51 ms 94148 KB Output is correct
5 Correct 51 ms 94148 KB Output is correct
6 Correct 44 ms 94180 KB Output is correct
7 Correct 44 ms 94240 KB Output is correct
8 Correct 50 ms 94176 KB Output is correct
9 Correct 46 ms 94292 KB Output is correct
10 Correct 46 ms 94284 KB Output is correct
11 Correct 50 ms 94628 KB Output is correct
12 Correct 50 ms 94308 KB Output is correct
13 Correct 46 ms 94228 KB Output is correct
14 Correct 45 ms 94664 KB Output is correct
15 Correct 47 ms 94700 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94228 KB Output is correct
2 Correct 49 ms 94188 KB Output is correct
3 Correct 49 ms 94260 KB Output is correct
4 Correct 44 ms 94176 KB Output is correct
5 Correct 47 ms 94252 KB Output is correct
6 Correct 45 ms 94256 KB Output is correct
7 Correct 47 ms 94156 KB Output is correct
8 Correct 46 ms 94200 KB Output is correct
9 Correct 43 ms 94164 KB Output is correct
10 Correct 46 ms 94392 KB Output is correct
11 Correct 46 ms 94588 KB Output is correct
12 Correct 47 ms 94264 KB Output is correct
13 Correct 50 ms 94224 KB Output is correct
14 Correct 47 ms 94700 KB Output is correct
15 Correct 47 ms 94688 KB Output is correct
16 Correct 50 ms 94540 KB Output is correct
17 Correct 61 ms 96140 KB Output is correct
18 Correct 49 ms 96676 KB Output is correct
19 Correct 47 ms 95692 KB Output is correct
20 Correct 45 ms 94480 KB Output is correct
21 Correct 45 ms 94452 KB Output is correct
22 Correct 49 ms 95692 KB Output is correct
23 Correct 51 ms 96304 KB Output is correct
24 Correct 58 ms 98320 KB Output is correct
25 Correct 46 ms 94948 KB Output is correct
26 Correct 52 ms 97476 KB Output is correct
27 Correct 48 ms 96340 KB Output is correct
28 Correct 56 ms 99020 KB Output is correct
29 Correct 62 ms 98496 KB Output is correct
30 Correct 46 ms 95440 KB Output is correct
31 Correct 49 ms 96452 KB Output is correct
32 Correct 48 ms 95820 KB Output is correct
33 Correct 71 ms 102708 KB Output is correct
34 Correct 67 ms 102708 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94252 KB Output is correct
2 Correct 45 ms 94156 KB Output is correct
3 Correct 48 ms 94248 KB Output is correct
4 Correct 44 ms 94212 KB Output is correct
5 Correct 48 ms 94228 KB Output is correct
6 Correct 45 ms 94156 KB Output is correct
7 Correct 50 ms 94168 KB Output is correct
8 Correct 44 ms 94140 KB Output is correct
9 Correct 47 ms 94152 KB Output is correct
10 Correct 45 ms 94292 KB Output is correct
11 Correct 46 ms 94552 KB Output is correct
12 Correct 47 ms 94408 KB Output is correct
13 Correct 44 ms 94168 KB Output is correct
14 Correct 45 ms 94624 KB Output is correct
15 Correct 49 ms 94668 KB Output is correct
16 Correct 50 ms 94612 KB Output is correct
17 Correct 51 ms 96204 KB Output is correct
18 Correct 52 ms 96716 KB Output is correct
19 Correct 47 ms 95672 KB Output is correct
20 Correct 46 ms 94408 KB Output is correct
21 Correct 46 ms 94516 KB Output is correct
22 Correct 49 ms 95788 KB Output is correct
23 Correct 50 ms 96196 KB Output is correct
24 Correct 57 ms 98296 KB Output is correct
25 Correct 46 ms 94848 KB Output is correct
26 Correct 56 ms 97516 KB Output is correct
27 Correct 50 ms 96376 KB Output is correct
28 Correct 56 ms 99020 KB Output is correct
29 Correct 60 ms 98536 KB Output is correct
30 Correct 49 ms 95396 KB Output is correct
31 Correct 54 ms 96464 KB Output is correct
32 Correct 49 ms 95820 KB Output is correct
33 Correct 72 ms 102744 KB Output is correct
34 Correct 71 ms 102704 KB Output is correct
35 Correct 74 ms 102760 KB Output is correct
36 Correct 51 ms 97132 KB Output is correct
37 Correct 96 ms 108616 KB Output is correct
38 Correct 103 ms 108124 KB Output is correct
39 Correct 105 ms 108264 KB Output is correct
40 Correct 97 ms 108168 KB Output is correct
41 Correct 101 ms 108224 KB Output is correct
42 Correct 72 ms 97680 KB Output is correct
43 Correct 61 ms 96588 KB Output is correct
44 Correct 49 ms 94620 KB Output is correct
45 Correct 195 ms 127208 KB Output is correct
46 Correct 195 ms 127236 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94244 KB Output is correct
2 Correct 56 ms 94236 KB Output is correct
3 Correct 45 ms 94156 KB Output is correct
4 Correct 45 ms 94348 KB Output is correct
5 Correct 47 ms 94172 KB Output is correct
6 Correct 48 ms 94304 KB Output is correct
7 Correct 48 ms 94192 KB Output is correct
8 Correct 50 ms 94220 KB Output is correct
9 Correct 46 ms 94156 KB Output is correct
10 Correct 45 ms 94392 KB Output is correct
11 Correct 46 ms 94776 KB Output is correct
12 Correct 45 ms 94252 KB Output is correct
13 Correct 44 ms 94292 KB Output is correct
14 Correct 48 ms 94668 KB Output is correct
15 Correct 48 ms 94624 KB Output is correct
16 Correct 48 ms 94592 KB Output is correct
17 Correct 53 ms 96132 KB Output is correct
18 Correct 69 ms 96688 KB Output is correct
19 Correct 57 ms 95692 KB Output is correct
20 Correct 48 ms 94364 KB Output is correct
21 Correct 46 ms 94572 KB Output is correct
22 Correct 47 ms 95692 KB Output is correct
23 Correct 52 ms 96400 KB Output is correct
24 Correct 54 ms 98308 KB Output is correct
25 Correct 49 ms 94924 KB Output is correct
26 Correct 52 ms 97560 KB Output is correct
27 Correct 51 ms 96268 KB Output is correct
28 Correct 58 ms 99020 KB Output is correct
29 Correct 58 ms 98512 KB Output is correct
30 Correct 51 ms 95444 KB Output is correct
31 Correct 52 ms 96460 KB Output is correct
32 Correct 52 ms 95820 KB Output is correct
33 Correct 68 ms 102732 KB Output is correct
34 Correct 69 ms 102680 KB Output is correct
35 Correct 75 ms 102756 KB Output is correct
36 Correct 52 ms 97228 KB Output is correct
37 Correct 99 ms 108700 KB Output is correct
38 Correct 97 ms 108196 KB Output is correct
39 Correct 94 ms 108196 KB Output is correct
40 Correct 103 ms 108260 KB Output is correct
41 Correct 98 ms 108376 KB Output is correct
42 Correct 56 ms 97844 KB Output is correct
43 Correct 56 ms 96592 KB Output is correct
44 Correct 54 ms 94672 KB Output is correct
45 Correct 197 ms 127228 KB Output is correct
46 Correct 199 ms 127368 KB Output is correct
47 Correct 391 ms 211888 KB Output is correct
48 Runtime error 481 ms 262144 KB Execution killed with signal 11
49 Halted 0 ms 0 KB -