oj.uz

Submission #733608

# Submission time Handle Problem Language Result Execution time Memory
733608 2023-05-01T04:43:02 Z SanguineChameleon Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 459 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();
		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);
			}
		}
		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 51 ms 94136 KB Output is correct
2 Correct 45 ms 94256 KB Output is correct
3 Correct 53 ms 94252 KB Output is correct
4 Correct 44 ms 94144 KB Output is correct
5 Correct 46 ms 94252 KB Output is correct
6 Correct 45 ms 94156 KB Output is correct
7 Correct 44 ms 94164 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94156 KB Output is correct
2 Correct 46 ms 94156 KB Output is correct
3 Correct 49 ms 94228 KB Output is correct
4 Correct 45 ms 94140 KB Output is correct
5 Correct 43 ms 94192 KB Output is correct
6 Correct 46 ms 94236 KB Output is correct
7 Correct 46 ms 94208 KB Output is correct
8 Correct 47 ms 94268 KB Output is correct
9 Correct 48 ms 94272 KB Output is correct
10 Correct 47 ms 94312 KB Output is correct
11 Correct 48 ms 94540 KB Output is correct
12 Correct 44 ms 94204 KB Output is correct
13 Correct 51 ms 94264 KB Output is correct
14 Correct 51 ms 94632 KB Output is correct
15 Correct 46 ms 94636 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 94148 KB Output is correct
2 Correct 44 ms 94144 KB Output is correct
3 Correct 46 ms 94144 KB Output is correct
4 Correct 45 ms 94156 KB Output is correct
5 Correct 47 ms 94208 KB Output is correct
6 Correct 49 ms 94208 KB Output is correct
7 Correct 46 ms 94196 KB Output is correct
8 Correct 44 ms 94160 KB Output is correct
9 Correct 44 ms 94208 KB Output is correct
10 Correct 46 ms 94360 KB Output is correct
11 Correct 48 ms 94644 KB Output is correct
12 Correct 44 ms 94284 KB Output is correct
13 Correct 45 ms 94184 KB Output is correct
14 Correct 46 ms 94676 KB Output is correct
15 Correct 45 ms 94684 KB Output is correct
16 Correct 46 ms 94612 KB Output is correct
17 Correct 48 ms 96076 KB Output is correct
18 Correct 50 ms 96716 KB Output is correct
19 Correct 49 ms 95688 KB Output is correct
20 Correct 47 ms 94444 KB Output is correct
21 Correct 51 ms 94540 KB Output is correct
22 Correct 47 ms 95772 KB Output is correct
23 Correct 49 ms 96280 KB Output is correct
24 Correct 58 ms 98268 KB Output is correct
25 Correct 56 ms 94864 KB Output is correct
26 Correct 54 ms 97516 KB Output is correct
27 Correct 53 ms 96376 KB Output is correct
28 Correct 55 ms 98968 KB Output is correct
29 Correct 61 ms 98548 KB Output is correct
30 Correct 58 ms 95392 KB Output is correct
31 Correct 53 ms 96432 KB Output is correct
32 Correct 49 ms 95748 KB Output is correct
33 Correct 80 ms 102628 KB Output is correct
34 Correct 64 ms 102696 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94136 KB Output is correct
2 Correct 46 ms 94152 KB Output is correct
3 Correct 45 ms 94172 KB Output is correct
4 Correct 48 ms 94220 KB Output is correct
5 Correct 46 ms 94180 KB Output is correct
6 Correct 49 ms 94156 KB Output is correct
7 Correct 53 ms 94152 KB Output is correct
8 Correct 46 ms 94156 KB Output is correct
9 Correct 45 ms 94272 KB Output is correct
10 Correct 50 ms 94284 KB Output is correct
11 Correct 46 ms 94648 KB Output is correct
12 Correct 44 ms 94260 KB Output is correct
13 Correct 54 ms 94240 KB Output is correct
14 Correct 53 ms 94796 KB Output is correct
15 Correct 46 ms 94668 KB Output is correct
16 Correct 46 ms 94604 KB Output is correct
17 Correct 53 ms 96076 KB Output is correct
18 Correct 54 ms 96664 KB Output is correct
19 Correct 49 ms 95700 KB Output is correct
20 Correct 48 ms 94412 KB Output is correct
21 Correct 45 ms 94600 KB Output is correct
22 Correct 49 ms 95824 KB Output is correct
23 Correct 56 ms 96204 KB Output is correct
24 Correct 56 ms 98288 KB Output is correct
25 Correct 50 ms 94968 KB Output is correct
26 Correct 53 ms 97548 KB Output is correct
27 Correct 57 ms 96332 KB Output is correct
28 Correct 63 ms 99028 KB Output is correct
29 Correct 65 ms 98508 KB Output is correct
30 Correct 49 ms 95480 KB Output is correct
31 Correct 52 ms 96548 KB Output is correct
32 Correct 54 ms 95820 KB Output is correct
33 Correct 70 ms 102736 KB Output is correct
34 Correct 75 ms 102732 KB Output is correct
35 Correct 69 ms 102860 KB Output is correct
36 Correct 54 ms 97020 KB Output is correct
37 Correct 85 ms 108664 KB Output is correct
38 Correct 77 ms 108136 KB Output is correct
39 Correct 87 ms 107980 KB Output is correct
40 Correct 82 ms 108136 KB Output is correct
41 Correct 84 ms 108180 KB Output is correct
42 Correct 66 ms 97768 KB Output is correct
43 Correct 57 ms 96496 KB Output is correct
44 Correct 62 ms 94700 KB Output is correct
45 Correct 206 ms 127244 KB Output is correct
46 Correct 174 ms 127360 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 94168 KB Output is correct
2 Correct 50 ms 94228 KB Output is correct
3 Correct 58 ms 94252 KB Output is correct
4 Correct 51 ms 94268 KB Output is correct
5 Correct 45 ms 94136 KB Output is correct
6 Correct 51 ms 94136 KB Output is correct
7 Correct 46 ms 94240 KB Output is correct
8 Correct 47 ms 94176 KB Output is correct
9 Correct 47 ms 94332 KB Output is correct
10 Correct 48 ms 94312 KB Output is correct
11 Correct 46 ms 94540 KB Output is correct
12 Correct 45 ms 94256 KB Output is correct
13 Correct 47 ms 94236 KB Output is correct
14 Correct 50 ms 94664 KB Output is correct
15 Correct 47 ms 94668 KB Output is correct
16 Correct 48 ms 94548 KB Output is correct
17 Correct 50 ms 96076 KB Output is correct
18 Correct 50 ms 96644 KB Output is correct
19 Correct 47 ms 95648 KB Output is correct
20 Correct 46 ms 94424 KB Output is correct
21 Correct 47 ms 94512 KB Output is correct
22 Correct 54 ms 95688 KB Output is correct
23 Correct 52 ms 96204 KB Output is correct
24 Correct 56 ms 98252 KB Output is correct
25 Correct 49 ms 94912 KB Output is correct
26 Correct 52 ms 97560 KB Output is correct
27 Correct 49 ms 96340 KB Output is correct
28 Correct 53 ms 98984 KB Output is correct
29 Correct 57 ms 98548 KB Output is correct
30 Correct 50 ms 95396 KB Output is correct
31 Correct 54 ms 96480 KB Output is correct
32 Correct 48 ms 95880 KB Output is correct
33 Correct 71 ms 102672 KB Output is correct
34 Correct 70 ms 102752 KB Output is correct
35 Correct 69 ms 102796 KB Output is correct
36 Correct 56 ms 97124 KB Output is correct
37 Correct 90 ms 108548 KB Output is correct
38 Correct 82 ms 108088 KB Output is correct
39 Correct 79 ms 107996 KB Output is correct
40 Correct 79 ms 108080 KB Output is correct
41 Correct 79 ms 108212 KB Output is correct
42 Correct 61 ms 97708 KB Output is correct
43 Correct 58 ms 96520 KB Output is correct
44 Correct 50 ms 94668 KB Output is correct
45 Correct 190 ms 127244 KB Output is correct
46 Correct 166 ms 127204 KB Output is correct
47 Correct 280 ms 211792 KB Output is correct
48 Runtime error 459 ms 262144 KB Execution killed with signal 11
49 Halted 0 ms 0 KB -