oj.uz

답안 #771241

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
771241 2023-07-02T17:06:40 Z IBory Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 267 ms 252500 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 2222222;
vector<int> G[MAX];
int D[MAX];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M, S, E;
	cin >> N >> M;
	map<pii, vector<int>> make;
	for (int i = 0; i < M; ++i) {
		int b, p;
		cin >> b >> p;
		if (i == 0) S = b;
		if (i == 1) E = b;
		make[{p, b % p}].push_back(b);
	}
	int node = N;

	for (auto& [q, v] : make) {
		auto [p, i] = q;
		vector<int> fr;
		for (int j = i; j < N; j += p) fr.push_back(j);
		int base = -1;
		for (int n = 0; n < fr.size(); ++n) {
			G[node].push_back(fr[n]);
			if (base != -1) G[base].push_back(node);
			base = node++;
		}
		base = -1;
		for (int n = fr.size() - 1; n >= 0; --n) {
			G[node].push_back(fr[n]);
			if (base != -1) G[base].push_back(node);
			base = node++;
		}
		for (int s : v) {
			int n = (s - i) / p;
			if (n) G[s].push_back(fr[n - 1]);
			if (n + 1 < fr.size()) G[s].push_back(fr[n + 1]);
			if (1 < n) G[s].push_back(node - (n - 1));
			if (n + 2 < fr.size()) G[s].push_back(node - 2 * fr.size() + n + 2);
		}
	}
	make.clear();

	memset(D, 0x3f, sizeof(D));
	D[S] = 0;
	queue<int> Q;
	Q.push(S);
	while (!Q.empty()) {
		int cur = Q.front(); Q.pop();
		for (int next : G[cur]) {
			if (D[next] < 1e9) continue;
			D[next] = D[cur] + 1;
			Q.push(next);
		}
	}

	cout << (D[E] > 1E9 ? -1 : D[E]);
	return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:23:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |  for (auto& [q, v] : make) {
      |             ^
skyscraper.cpp:24:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |   auto [p, i] = q;
      |        ^
skyscraper.cpp:28:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for (int n = 0; n < fr.size(); ++n) {
      |                   ~~^~~~~~~~~~~
skyscraper.cpp:42:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    if (n + 1 < fr.size()) G[s].push_back(fr[n + 1]);
      |        ~~~~~~^~~~~~~~~~~
skyscraper.cpp:44:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |    if (n + 2 < fr.size()) G[s].push_back(node - 2 * fr.size() + n + 2);
      |        ~~~~~~^~~~~~~~~~~
skyscraper.cpp:62:14: warning: 'E' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |  cout << (D[E] > 1E9 ? -1 : D[E]);
      |           ~~~^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 61136 KB Output is correct
2 Correct 28 ms 61160 KB Output is correct
3 Correct 28 ms 61056 KB Output is correct
4 Correct 29 ms 61196 KB Output is correct
5 Correct 29 ms 61180 KB Output is correct
6 Correct 28 ms 61152 KB Output is correct
7 Correct 29 ms 61140 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 61152 KB Output is correct
2 Correct 29 ms 61192 KB Output is correct
3 Correct 35 ms 61200 KB Output is correct
4 Correct 29 ms 61196 KB Output is correct
5 Correct 29 ms 61168 KB Output is correct
6 Correct 30 ms 61188 KB Output is correct
7 Correct 31 ms 61140 KB Output is correct
8 Correct 35 ms 61140 KB Output is correct
9 Correct 29 ms 61140 KB Output is correct
10 Correct 36 ms 61276 KB Output is correct
11 Correct 30 ms 61516 KB Output is correct
12 Correct 29 ms 61196 KB Output is correct
13 Correct 30 ms 61148 KB Output is correct
14 Correct 31 ms 61752 KB Output is correct
15 Correct 34 ms 61772 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 61184 KB Output is correct
2 Correct 29 ms 61140 KB Output is correct
3 Correct 29 ms 61140 KB Output is correct
4 Correct 31 ms 61060 KB Output is correct
5 Correct 29 ms 61132 KB Output is correct
6 Correct 29 ms 61192 KB Output is correct
7 Correct 30 ms 61140 KB Output is correct
8 Correct 28 ms 61092 KB Output is correct
9 Correct 30 ms 61136 KB Output is correct
10 Correct 30 ms 61324 KB Output is correct
11 Correct 33 ms 61640 KB Output is correct
12 Correct 28 ms 61268 KB Output is correct
13 Correct 28 ms 61132 KB Output is correct
14 Correct 30 ms 61720 KB Output is correct
15 Correct 30 ms 61780 KB Output is correct
16 Correct 29 ms 61524 KB Output is correct
17 Correct 37 ms 62308 KB Output is correct
18 Correct 30 ms 61724 KB Output is correct
19 Correct 30 ms 61472 KB Output is correct
20 Correct 32 ms 61388 KB Output is correct
21 Correct 34 ms 61472 KB Output is correct
22 Correct 38 ms 61600 KB Output is correct
23 Correct 33 ms 61640 KB Output is correct
24 Correct 35 ms 62200 KB Output is correct
25 Correct 31 ms 61864 KB Output is correct
26 Correct 30 ms 61616 KB Output is correct
27 Correct 37 ms 61568 KB Output is correct
28 Correct 37 ms 62824 KB Output is correct
29 Correct 38 ms 65120 KB Output is correct
30 Correct 36 ms 62268 KB Output is correct
31 Correct 42 ms 63284 KB Output is correct
32 Correct 33 ms 62684 KB Output is correct
33 Correct 56 ms 68920 KB Output is correct
34 Correct 50 ms 68952 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 61120 KB Output is correct
2 Correct 29 ms 61140 KB Output is correct
3 Correct 33 ms 61088 KB Output is correct
4 Correct 36 ms 61148 KB Output is correct
5 Correct 32 ms 61140 KB Output is correct
6 Correct 30 ms 61100 KB Output is correct
7 Correct 29 ms 61188 KB Output is correct
8 Correct 28 ms 61088 KB Output is correct
9 Correct 28 ms 61124 KB Output is correct
10 Correct 30 ms 61324 KB Output is correct
11 Correct 34 ms 61640 KB Output is correct
12 Correct 29 ms 61276 KB Output is correct
13 Correct 29 ms 61148 KB Output is correct
14 Correct 31 ms 61780 KB Output is correct
15 Correct 31 ms 61752 KB Output is correct
16 Correct 31 ms 61524 KB Output is correct
17 Correct 33 ms 62272 KB Output is correct
18 Correct 39 ms 61608 KB Output is correct
19 Correct 30 ms 61440 KB Output is correct
20 Correct 30 ms 61336 KB Output is correct
21 Correct 30 ms 61388 KB Output is correct
22 Correct 30 ms 61632 KB Output is correct
23 Correct 31 ms 61728 KB Output is correct
24 Correct 32 ms 62164 KB Output is correct
25 Correct 38 ms 61904 KB Output is correct
26 Correct 34 ms 61676 KB Output is correct
27 Correct 31 ms 61668 KB Output is correct
28 Correct 34 ms 62848 KB Output is correct
29 Correct 39 ms 65004 KB Output is correct
30 Correct 31 ms 62284 KB Output is correct
31 Correct 38 ms 63228 KB Output is correct
32 Correct 33 ms 62720 KB Output is correct
33 Correct 50 ms 68896 KB Output is correct
34 Correct 49 ms 68940 KB Output is correct
35 Correct 73 ms 70476 KB Output is correct
36 Correct 33 ms 62864 KB Output is correct
37 Correct 70 ms 74220 KB Output is correct
38 Correct 72 ms 74772 KB Output is correct
39 Correct 84 ms 74796 KB Output is correct
40 Correct 85 ms 74700 KB Output is correct
41 Correct 89 ms 74728 KB Output is correct
42 Correct 40 ms 62180 KB Output is correct
43 Correct 42 ms 62228 KB Output is correct
44 Correct 34 ms 61852 KB Output is correct
45 Correct 128 ms 94888 KB Output is correct
46 Correct 140 ms 94932 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 61104 KB Output is correct
2 Correct 29 ms 61176 KB Output is correct
3 Correct 30 ms 61180 KB Output is correct
4 Correct 34 ms 61140 KB Output is correct
5 Correct 35 ms 61076 KB Output is correct
6 Correct 30 ms 61148 KB Output is correct
7 Correct 29 ms 61140 KB Output is correct
8 Correct 32 ms 61124 KB Output is correct
9 Correct 31 ms 61148 KB Output is correct
10 Correct 29 ms 61268 KB Output is correct
11 Correct 33 ms 61636 KB Output is correct
12 Correct 29 ms 61264 KB Output is correct
13 Correct 30 ms 61256 KB Output is correct
14 Correct 30 ms 61816 KB Output is correct
15 Correct 31 ms 61728 KB Output is correct
16 Correct 29 ms 61516 KB Output is correct
17 Correct 38 ms 62332 KB Output is correct
18 Correct 30 ms 61728 KB Output is correct
19 Correct 36 ms 61460 KB Output is correct
20 Correct 30 ms 61360 KB Output is correct
21 Correct 30 ms 61432 KB Output is correct
22 Correct 30 ms 61532 KB Output is correct
23 Correct 30 ms 61620 KB Output is correct
24 Correct 31 ms 62232 KB Output is correct
25 Correct 36 ms 61916 KB Output is correct
26 Correct 30 ms 61652 KB Output is correct
27 Correct 30 ms 61576 KB Output is correct
28 Correct 41 ms 62880 KB Output is correct
29 Correct 38 ms 65104 KB Output is correct
30 Correct 32 ms 62236 KB Output is correct
31 Correct 38 ms 63368 KB Output is correct
32 Correct 33 ms 62684 KB Output is correct
33 Correct 48 ms 68880 KB Output is correct
34 Correct 48 ms 68952 KB Output is correct
35 Correct 59 ms 70552 KB Output is correct
36 Correct 34 ms 62776 KB Output is correct
37 Correct 71 ms 74260 KB Output is correct
38 Correct 72 ms 74760 KB Output is correct
39 Correct 78 ms 74752 KB Output is correct
40 Correct 75 ms 74740 KB Output is correct
41 Correct 84 ms 74672 KB Output is correct
42 Correct 42 ms 62196 KB Output is correct
43 Correct 34 ms 62256 KB Output is correct
44 Correct 32 ms 61820 KB Output is correct
45 Correct 131 ms 94904 KB Output is correct
46 Correct 139 ms 94932 KB Output is correct
47 Correct 173 ms 110448 KB Output is correct
48 Correct 74 ms 78632 KB Output is correct
49 Correct 71 ms 72860 KB Output is correct
50 Correct 69 ms 72020 KB Output is correct
51 Correct 103 ms 84832 KB Output is correct
52 Correct 108 ms 86612 KB Output is correct
53 Correct 56 ms 70136 KB Output is correct
54 Correct 49 ms 63008 KB Output is correct
55 Correct 46 ms 64668 KB Output is correct
56 Correct 41 ms 64140 KB Output is correct
57 Correct 111 ms 88300 KB Output is correct
58 Correct 43 ms 65764 KB Output is correct
59 Correct 45 ms 67732 KB Output is correct
60 Correct 51 ms 69512 KB Output is correct
61 Correct 50 ms 68748 KB Output is correct
62 Correct 120 ms 95744 KB Output is correct
63 Runtime error 267 ms 252500 KB Execution killed with signal 11
64 Halted 0 ms 0 KB -