oj.uz

Submission #733612

# Submission time Handle Problem Language Result Execution time Memory
733612 2023-05-01T04:49:29 Z SanguineChameleon Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 283 ms 177184 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 = 3e6 + 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++;
				if (cnt == maxC) {
					exit(0);
				}
			}
		}
	}
	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++;
				if (cnt == maxC) {
					exit(0);
				}
			}
		}
		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]]);
			}
		}
	}
	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();
		if (u < N) {
			for (auto v: adj0[u]) {
				if (dist[u] < dist[v]) {
					dist[v] = dist[u];
					q.push_front(v);
				}
			}
		}
		else 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 42 ms 83204 KB Output is correct
2 Correct 38 ms 83104 KB Output is correct
3 Correct 40 ms 83180 KB Output is correct
4 Correct 40 ms 83096 KB Output is correct
5 Correct 41 ms 83152 KB Output is correct
6 Correct 40 ms 83104 KB Output is correct
7 Correct 46 ms 83196 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 83112 KB Output is correct
2 Correct 41 ms 83200 KB Output is correct
3 Correct 43 ms 83220 KB Output is correct
4 Correct 45 ms 83196 KB Output is correct
5 Correct 42 ms 83156 KB Output is correct
6 Correct 41 ms 83092 KB Output is correct
7 Correct 47 ms 83148 KB Output is correct
8 Correct 40 ms 83148 KB Output is correct
9 Correct 40 ms 83156 KB Output is correct
10 Correct 41 ms 83260 KB Output is correct
11 Correct 40 ms 83364 KB Output is correct
12 Correct 46 ms 83148 KB Output is correct
13 Correct 46 ms 83156 KB Output is correct
14 Correct 40 ms 83460 KB Output is correct
15 Correct 41 ms 83356 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 83212 KB Output is correct
2 Correct 41 ms 83100 KB Output is correct
3 Correct 39 ms 83156 KB Output is correct
4 Correct 41 ms 83120 KB Output is correct
5 Correct 40 ms 83104 KB Output is correct
6 Correct 40 ms 83148 KB Output is correct
7 Correct 40 ms 83156 KB Output is correct
8 Correct 42 ms 83284 KB Output is correct
9 Correct 40 ms 83196 KB Output is correct
10 Correct 41 ms 83248 KB Output is correct
11 Correct 49 ms 83316 KB Output is correct
12 Correct 43 ms 83148 KB Output is correct
13 Correct 41 ms 83184 KB Output is correct
14 Correct 42 ms 83360 KB Output is correct
15 Correct 40 ms 83404 KB Output is correct
16 Correct 39 ms 83412 KB Output is correct
17 Correct 51 ms 84188 KB Output is correct
18 Correct 46 ms 84556 KB Output is correct
19 Correct 45 ms 84044 KB Output is correct
20 Correct 41 ms 83344 KB Output is correct
21 Correct 40 ms 83368 KB Output is correct
22 Correct 43 ms 84044 KB Output is correct
23 Correct 44 ms 84300 KB Output is correct
24 Correct 48 ms 85372 KB Output is correct
25 Correct 43 ms 83600 KB Output is correct
26 Correct 45 ms 84916 KB Output is correct
27 Correct 44 ms 84360 KB Output is correct
28 Correct 48 ms 85788 KB Output is correct
29 Correct 52 ms 85452 KB Output is correct
30 Correct 41 ms 83808 KB Output is correct
31 Correct 44 ms 84472 KB Output is correct
32 Correct 42 ms 84128 KB Output is correct
33 Correct 55 ms 87712 KB Output is correct
34 Correct 54 ms 87640 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 83148 KB Output is correct
2 Correct 40 ms 83224 KB Output is correct
3 Correct 39 ms 83148 KB Output is correct
4 Correct 40 ms 83148 KB Output is correct
5 Correct 39 ms 83192 KB Output is correct
6 Correct 39 ms 83144 KB Output is correct
7 Correct 38 ms 83208 KB Output is correct
8 Correct 39 ms 83164 KB Output is correct
9 Correct 40 ms 83236 KB Output is correct
10 Correct 43 ms 83276 KB Output is correct
11 Correct 41 ms 83336 KB Output is correct
12 Correct 39 ms 83148 KB Output is correct
13 Correct 39 ms 83176 KB Output is correct
14 Correct 42 ms 83436 KB Output is correct
15 Correct 41 ms 83444 KB Output is correct
16 Correct 46 ms 83384 KB Output is correct
17 Correct 44 ms 84220 KB Output is correct
18 Correct 46 ms 84452 KB Output is correct
19 Correct 43 ms 83924 KB Output is correct
20 Correct 41 ms 83336 KB Output is correct
21 Correct 42 ms 83404 KB Output is correct
22 Correct 44 ms 83992 KB Output is correct
23 Correct 48 ms 84312 KB Output is correct
24 Correct 53 ms 85408 KB Output is correct
25 Correct 42 ms 83524 KB Output is correct
26 Correct 52 ms 85056 KB Output is correct
27 Correct 47 ms 84368 KB Output is correct
28 Correct 55 ms 85768 KB Output is correct
29 Correct 53 ms 85452 KB Output is correct
30 Correct 41 ms 83820 KB Output is correct
31 Correct 46 ms 84372 KB Output is correct
32 Correct 44 ms 84036 KB Output is correct
33 Correct 57 ms 87668 KB Output is correct
34 Correct 54 ms 87748 KB Output is correct
35 Correct 58 ms 87760 KB Output is correct
36 Correct 51 ms 84732 KB Output is correct
37 Correct 63 ms 90992 KB Output is correct
38 Correct 64 ms 90652 KB Output is correct
39 Correct 68 ms 90628 KB Output is correct
40 Correct 63 ms 90700 KB Output is correct
41 Correct 63 ms 90700 KB Output is correct
42 Correct 49 ms 85068 KB Output is correct
43 Correct 52 ms 84548 KB Output is correct
44 Correct 49 ms 83532 KB Output is correct
45 Correct 185 ms 100944 KB Output is correct
46 Correct 139 ms 100940 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 83208 KB Output is correct
2 Correct 43 ms 83144 KB Output is correct
3 Correct 45 ms 83148 KB Output is correct
4 Correct 45 ms 83216 KB Output is correct
5 Correct 41 ms 83100 KB Output is correct
6 Correct 39 ms 83212 KB Output is correct
7 Correct 41 ms 83168 KB Output is correct
8 Correct 40 ms 83144 KB Output is correct
9 Correct 42 ms 83176 KB Output is correct
10 Correct 42 ms 83200 KB Output is correct
11 Correct 40 ms 83348 KB Output is correct
12 Correct 41 ms 83152 KB Output is correct
13 Correct 40 ms 83156 KB Output is correct
14 Correct 41 ms 83412 KB Output is correct
15 Correct 41 ms 83392 KB Output is correct
16 Correct 43 ms 83404 KB Output is correct
17 Correct 44 ms 84180 KB Output is correct
18 Correct 43 ms 84492 KB Output is correct
19 Correct 42 ms 83948 KB Output is correct
20 Correct 41 ms 83280 KB Output is correct
21 Correct 41 ms 83276 KB Output is correct
22 Correct 42 ms 84012 KB Output is correct
23 Correct 43 ms 84304 KB Output is correct
24 Correct 48 ms 85308 KB Output is correct
25 Correct 43 ms 83616 KB Output is correct
26 Correct 49 ms 84880 KB Output is correct
27 Correct 43 ms 84300 KB Output is correct
28 Correct 52 ms 85876 KB Output is correct
29 Correct 50 ms 85444 KB Output is correct
30 Correct 45 ms 83772 KB Output is correct
31 Correct 48 ms 84360 KB Output is correct
32 Correct 42 ms 83972 KB Output is correct
33 Correct 63 ms 87732 KB Output is correct
34 Correct 52 ms 87644 KB Output is correct
35 Correct 57 ms 87772 KB Output is correct
36 Correct 46 ms 84668 KB Output is correct
37 Correct 68 ms 91028 KB Output is correct
38 Correct 67 ms 90612 KB Output is correct
39 Correct 63 ms 90588 KB Output is correct
40 Correct 65 ms 90704 KB Output is correct
41 Correct 64 ms 90696 KB Output is correct
42 Correct 50 ms 85184 KB Output is correct
43 Correct 46 ms 84496 KB Output is correct
44 Correct 53 ms 83576 KB Output is correct
45 Correct 167 ms 101004 KB Output is correct
46 Correct 124 ms 100896 KB Output is correct
47 Correct 190 ms 145712 KB Output is correct
48 Correct 227 ms 164664 KB Output is correct
49 Correct 191 ms 148800 KB Output is correct
50 Correct 189 ms 150344 KB Output is correct
51 Incorrect 283 ms 177184 KB Output isn't correct
52 Halted 0 ms 0 KB -