oj.uz

답안 #733613

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
733613 2023-05-01T04:51:19 Z SanguineChameleon Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 787 ms 247392 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 = 4e6 + 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

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 110548 KB Output is correct
2 Correct 50 ms 110520 KB Output is correct
3 Correct 54 ms 110500 KB Output is correct
4 Correct 50 ms 110576 KB Output is correct
5 Correct 50 ms 110600 KB Output is correct
6 Correct 51 ms 110596 KB Output is correct
7 Correct 57 ms 110544 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 110540 KB Output is correct
2 Correct 52 ms 110620 KB Output is correct
3 Correct 51 ms 110620 KB Output is correct
4 Correct 53 ms 110540 KB Output is correct
5 Correct 53 ms 110616 KB Output is correct
6 Correct 54 ms 110508 KB Output is correct
7 Correct 55 ms 110612 KB Output is correct
8 Correct 53 ms 110544 KB Output is correct
9 Correct 60 ms 110656 KB Output is correct
10 Correct 51 ms 110580 KB Output is correct
11 Correct 55 ms 110752 KB Output is correct
12 Correct 55 ms 110628 KB Output is correct
13 Correct 53 ms 110584 KB Output is correct
14 Correct 56 ms 110872 KB Output is correct
15 Correct 55 ms 110796 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 110684 KB Output is correct
2 Correct 55 ms 110576 KB Output is correct
3 Correct 53 ms 110616 KB Output is correct
4 Correct 52 ms 110520 KB Output is correct
5 Correct 63 ms 110616 KB Output is correct
6 Correct 55 ms 110540 KB Output is correct
7 Correct 56 ms 110620 KB Output is correct
8 Correct 52 ms 110548 KB Output is correct
9 Correct 52 ms 110632 KB Output is correct
10 Correct 55 ms 110616 KB Output is correct
11 Correct 61 ms 110744 KB Output is correct
12 Correct 56 ms 110684 KB Output is correct
13 Correct 56 ms 110644 KB Output is correct
14 Correct 56 ms 110848 KB Output is correct
15 Correct 55 ms 110796 KB Output is correct
16 Correct 53 ms 110744 KB Output is correct
17 Correct 54 ms 111564 KB Output is correct
18 Correct 60 ms 111952 KB Output is correct
19 Correct 59 ms 111440 KB Output is correct
20 Correct 55 ms 110668 KB Output is correct
21 Correct 51 ms 110756 KB Output is correct
22 Correct 54 ms 111416 KB Output is correct
23 Correct 54 ms 111724 KB Output is correct
24 Correct 64 ms 112808 KB Output is correct
25 Correct 52 ms 110984 KB Output is correct
26 Correct 55 ms 112284 KB Output is correct
27 Correct 58 ms 111740 KB Output is correct
28 Correct 58 ms 113164 KB Output is correct
29 Correct 74 ms 112872 KB Output is correct
30 Correct 56 ms 111296 KB Output is correct
31 Correct 60 ms 111844 KB Output is correct
32 Correct 56 ms 111484 KB Output is correct
33 Correct 70 ms 115108 KB Output is correct
34 Correct 66 ms 115052 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 110600 KB Output is correct
2 Correct 66 ms 110612 KB Output is correct
3 Correct 59 ms 110620 KB Output is correct
4 Correct 57 ms 110544 KB Output is correct
5 Correct 58 ms 110540 KB Output is correct
6 Correct 58 ms 110544 KB Output is correct
7 Correct 54 ms 110668 KB Output is correct
8 Correct 53 ms 110512 KB Output is correct
9 Correct 55 ms 110540 KB Output is correct
10 Correct 61 ms 110696 KB Output is correct
11 Correct 56 ms 110780 KB Output is correct
12 Correct 53 ms 110588 KB Output is correct
13 Correct 52 ms 110648 KB Output is correct
14 Correct 52 ms 110768 KB Output is correct
15 Correct 56 ms 110804 KB Output is correct
16 Correct 54 ms 110696 KB Output is correct
17 Correct 58 ms 111556 KB Output is correct
18 Correct 59 ms 111940 KB Output is correct
19 Correct 54 ms 111552 KB Output is correct
20 Correct 59 ms 110904 KB Output is correct
21 Correct 57 ms 110664 KB Output is correct
22 Correct 57 ms 111432 KB Output is correct
23 Correct 57 ms 111720 KB Output is correct
24 Correct 59 ms 112756 KB Output is correct
25 Correct 58 ms 110964 KB Output is correct
26 Correct 65 ms 112380 KB Output is correct
27 Correct 60 ms 111648 KB Output is correct
28 Correct 61 ms 113100 KB Output is correct
29 Correct 64 ms 112904 KB Output is correct
30 Correct 59 ms 111268 KB Output is correct
31 Correct 64 ms 111848 KB Output is correct
32 Correct 65 ms 111464 KB Output is correct
33 Correct 70 ms 115144 KB Output is correct
34 Correct 72 ms 115144 KB Output is correct
35 Correct 70 ms 115172 KB Output is correct
36 Correct 61 ms 112032 KB Output is correct
37 Correct 80 ms 118504 KB Output is correct
38 Correct 82 ms 118052 KB Output is correct
39 Correct 74 ms 117964 KB Output is correct
40 Correct 79 ms 118052 KB Output is correct
41 Correct 83 ms 118124 KB Output is correct
42 Correct 65 ms 112600 KB Output is correct
43 Correct 60 ms 111872 KB Output is correct
44 Correct 58 ms 111004 KB Output is correct
45 Correct 156 ms 128372 KB Output is correct
46 Correct 155 ms 128316 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 110620 KB Output is correct
2 Correct 54 ms 110604 KB Output is correct
3 Correct 68 ms 110540 KB Output is correct
4 Correct 62 ms 110516 KB Output is correct
5 Correct 55 ms 110544 KB Output is correct
6 Correct 53 ms 110584 KB Output is correct
7 Correct 52 ms 110580 KB Output is correct
8 Correct 56 ms 110540 KB Output is correct
9 Correct 56 ms 110528 KB Output is correct
10 Correct 56 ms 110704 KB Output is correct
11 Correct 53 ms 110836 KB Output is correct
12 Correct 54 ms 110632 KB Output is correct
13 Correct 52 ms 110620 KB Output is correct
14 Correct 55 ms 110852 KB Output is correct
15 Correct 60 ms 110844 KB Output is correct
16 Correct 56 ms 110704 KB Output is correct
17 Correct 55 ms 111564 KB Output is correct
18 Correct 62 ms 111960 KB Output is correct
19 Correct 53 ms 111372 KB Output is correct
20 Correct 55 ms 110720 KB Output is correct
21 Correct 64 ms 110756 KB Output is correct
22 Correct 65 ms 111436 KB Output is correct
23 Correct 57 ms 111752 KB Output is correct
24 Correct 63 ms 112732 KB Output is correct
25 Correct 55 ms 110924 KB Output is correct
26 Correct 58 ms 112284 KB Output is correct
27 Correct 57 ms 111736 KB Output is correct
28 Correct 63 ms 113168 KB Output is correct
29 Correct 63 ms 112796 KB Output is correct
30 Correct 58 ms 111260 KB Output is correct
31 Correct 59 ms 111844 KB Output is correct
32 Correct 61 ms 111396 KB Output is correct
33 Correct 78 ms 115020 KB Output is correct
34 Correct 71 ms 115040 KB Output is correct
35 Correct 74 ms 115204 KB Output is correct
36 Correct 56 ms 112132 KB Output is correct
37 Correct 75 ms 118336 KB Output is correct
38 Correct 76 ms 118104 KB Output is correct
39 Correct 75 ms 117964 KB Output is correct
40 Correct 86 ms 118032 KB Output is correct
41 Correct 88 ms 118056 KB Output is correct
42 Correct 61 ms 112524 KB Output is correct
43 Correct 59 ms 111972 KB Output is correct
44 Correct 55 ms 110912 KB Output is correct
45 Correct 200 ms 128244 KB Output is correct
46 Correct 152 ms 128340 KB Output is correct
47 Correct 203 ms 173208 KB Output is correct
48 Correct 256 ms 192012 KB Output is correct
49 Correct 204 ms 176244 KB Output is correct
50 Correct 242 ms 177620 KB Output is correct
51 Correct 333 ms 232088 KB Output is correct
52 Correct 366 ms 247392 KB Output is correct
53 Correct 69 ms 115648 KB Output is correct
54 Correct 56 ms 111864 KB Output is correct
55 Correct 65 ms 113980 KB Output is correct
56 Correct 68 ms 113224 KB Output is correct
57 Correct 94 ms 126836 KB Output is correct
58 Correct 88 ms 124868 KB Output is correct
59 Correct 137 ms 146224 KB Output is correct
60 Correct 259 ms 205212 KB Output is correct
61 Correct 152 ms 155340 KB Output is correct
62 Correct 272 ms 205188 KB Output is correct
63 Correct 586 ms 192024 KB Output is correct
64 Correct 787 ms 210268 KB Output is correct
65 Incorrect 385 ms 235728 KB Output isn't correct
66 Halted 0 ms 0 KB -