oj.uz

Submission #771233

# Submission time Handle Problem Language Result Execution time Memory
771233 2023-07-02T16:54:39 Z IBory Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 564 ms 262144 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 4444444;
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

# Verdict Execution time Memory Grader output
1 Correct 55 ms 122024 KB Output is correct
2 Correct 61 ms 122008 KB Output is correct
3 Correct 60 ms 121992 KB Output is correct
4 Correct 59 ms 122056 KB Output is correct
5 Correct 54 ms 122068 KB Output is correct
6 Correct 54 ms 122008 KB Output is correct
7 Correct 65 ms 122060 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 122076 KB Output is correct
2 Correct 54 ms 121972 KB Output is correct
3 Correct 54 ms 122064 KB Output is correct
4 Correct 55 ms 122040 KB Output is correct
5 Correct 54 ms 122060 KB Output is correct
6 Correct 55 ms 122072 KB Output is correct
7 Correct 54 ms 122028 KB Output is correct
8 Correct 58 ms 122076 KB Output is correct
9 Correct 58 ms 122096 KB Output is correct
10 Correct 56 ms 122096 KB Output is correct
11 Correct 59 ms 122472 KB Output is correct
12 Correct 63 ms 122096 KB Output is correct
13 Correct 59 ms 122056 KB Output is correct
14 Correct 58 ms 122672 KB Output is correct
15 Correct 59 ms 122612 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 122072 KB Output is correct
2 Correct 56 ms 121988 KB Output is correct
3 Correct 56 ms 122064 KB Output is correct
4 Correct 62 ms 121952 KB Output is correct
5 Correct 57 ms 122068 KB Output is correct
6 Correct 58 ms 122000 KB Output is correct
7 Correct 58 ms 122088 KB Output is correct
8 Correct 59 ms 122080 KB Output is correct
9 Correct 57 ms 122092 KB Output is correct
10 Correct 57 ms 122216 KB Output is correct
11 Correct 68 ms 122452 KB Output is correct
12 Correct 67 ms 122156 KB Output is correct
13 Correct 56 ms 122096 KB Output is correct
14 Correct 62 ms 122616 KB Output is correct
15 Correct 65 ms 122584 KB Output is correct
16 Correct 57 ms 122396 KB Output is correct
17 Correct 59 ms 123220 KB Output is correct
18 Correct 58 ms 122628 KB Output is correct
19 Correct 58 ms 122352 KB Output is correct
20 Correct 64 ms 122292 KB Output is correct
21 Correct 55 ms 122368 KB Output is correct
22 Correct 63 ms 122520 KB Output is correct
23 Correct 63 ms 122572 KB Output is correct
24 Correct 59 ms 123028 KB Output is correct
25 Correct 59 ms 122816 KB Output is correct
26 Correct 56 ms 122572 KB Output is correct
27 Correct 59 ms 122568 KB Output is correct
28 Correct 61 ms 123660 KB Output is correct
29 Correct 66 ms 125928 KB Output is correct
30 Correct 64 ms 123176 KB Output is correct
31 Correct 62 ms 124228 KB Output is correct
32 Correct 60 ms 123576 KB Output is correct
33 Correct 76 ms 129816 KB Output is correct
34 Correct 80 ms 129852 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 122064 KB Output is correct
2 Correct 56 ms 122068 KB Output is correct
3 Correct 55 ms 122024 KB Output is correct
4 Correct 56 ms 122060 KB Output is correct
5 Correct 56 ms 122060 KB Output is correct
6 Correct 56 ms 122068 KB Output is correct
7 Correct 61 ms 121956 KB Output is correct
8 Correct 56 ms 121960 KB Output is correct
9 Correct 56 ms 122068 KB Output is correct
10 Correct 63 ms 122104 KB Output is correct
11 Correct 56 ms 122492 KB Output is correct
12 Correct 62 ms 122060 KB Output is correct
13 Correct 58 ms 122060 KB Output is correct
14 Correct 69 ms 122600 KB Output is correct
15 Correct 58 ms 122692 KB Output is correct
16 Correct 57 ms 122408 KB Output is correct
17 Correct 60 ms 123120 KB Output is correct
18 Correct 55 ms 122528 KB Output is correct
19 Correct 56 ms 122380 KB Output is correct
20 Correct 62 ms 122316 KB Output is correct
21 Correct 59 ms 122324 KB Output is correct
22 Correct 56 ms 122512 KB Output is correct
23 Correct 59 ms 122576 KB Output is correct
24 Correct 58 ms 122996 KB Output is correct
25 Correct 59 ms 122744 KB Output is correct
26 Correct 65 ms 122580 KB Output is correct
27 Correct 60 ms 122500 KB Output is correct
28 Correct 60 ms 123724 KB Output is correct
29 Correct 69 ms 125916 KB Output is correct
30 Correct 58 ms 123108 KB Output is correct
31 Correct 61 ms 124136 KB Output is correct
32 Correct 65 ms 123568 KB Output is correct
33 Correct 89 ms 129780 KB Output is correct
34 Correct 76 ms 129720 KB Output is correct
35 Correct 85 ms 131652 KB Output is correct
36 Correct 59 ms 123800 KB Output is correct
37 Correct 97 ms 135328 KB Output is correct
38 Correct 102 ms 135872 KB Output is correct
39 Correct 111 ms 135948 KB Output is correct
40 Correct 123 ms 135900 KB Output is correct
41 Correct 100 ms 135884 KB Output is correct
42 Correct 65 ms 123364 KB Output is correct
43 Correct 61 ms 123308 KB Output is correct
44 Correct 62 ms 122988 KB Output is correct
45 Correct 156 ms 156028 KB Output is correct
46 Correct 160 ms 155932 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 122068 KB Output is correct
2 Correct 60 ms 122044 KB Output is correct
3 Correct 55 ms 121948 KB Output is correct
4 Correct 56 ms 122072 KB Output is correct
5 Correct 66 ms 122068 KB Output is correct
6 Correct 57 ms 121996 KB Output is correct
7 Correct 55 ms 122060 KB Output is correct
8 Correct 58 ms 121960 KB Output is correct
9 Correct 67 ms 122060 KB Output is correct
10 Correct 61 ms 122140 KB Output is correct
11 Correct 57 ms 122444 KB Output is correct
12 Correct 65 ms 122120 KB Output is correct
13 Correct 58 ms 122124 KB Output is correct
14 Correct 58 ms 122680 KB Output is correct
15 Correct 58 ms 122692 KB Output is correct
16 Correct 58 ms 122412 KB Output is correct
17 Correct 60 ms 123124 KB Output is correct
18 Correct 60 ms 122632 KB Output is correct
19 Correct 56 ms 122348 KB Output is correct
20 Correct 61 ms 122288 KB Output is correct
21 Correct 56 ms 122352 KB Output is correct
22 Correct 58 ms 122528 KB Output is correct
23 Correct 57 ms 122616 KB Output is correct
24 Correct 60 ms 123072 KB Output is correct
25 Correct 58 ms 122720 KB Output is correct
26 Correct 57 ms 122612 KB Output is correct
27 Correct 58 ms 122456 KB Output is correct
28 Correct 59 ms 123664 KB Output is correct
29 Correct 66 ms 125952 KB Output is correct
30 Correct 67 ms 123108 KB Output is correct
31 Correct 66 ms 124192 KB Output is correct
32 Correct 66 ms 123556 KB Output is correct
33 Correct 77 ms 129844 KB Output is correct
34 Correct 78 ms 129732 KB Output is correct
35 Correct 88 ms 131576 KB Output is correct
36 Correct 62 ms 123696 KB Output is correct
37 Correct 101 ms 135260 KB Output is correct
38 Correct 116 ms 135836 KB Output is correct
39 Correct 104 ms 135920 KB Output is correct
40 Correct 98 ms 135892 KB Output is correct
41 Correct 97 ms 135852 KB Output is correct
42 Correct 60 ms 123332 KB Output is correct
43 Correct 69 ms 123208 KB Output is correct
44 Correct 60 ms 122984 KB Output is correct
45 Correct 156 ms 156036 KB Output is correct
46 Correct 176 ms 155980 KB Output is correct
47 Correct 205 ms 171624 KB Output is correct
48 Correct 105 ms 139716 KB Output is correct
49 Correct 87 ms 133976 KB Output is correct
50 Correct 85 ms 133140 KB Output is correct
51 Correct 140 ms 146092 KB Output is correct
52 Correct 138 ms 147840 KB Output is correct
53 Correct 90 ms 131388 KB Output is correct
54 Correct 63 ms 123980 KB Output is correct
55 Correct 65 ms 125436 KB Output is correct
56 Correct 69 ms 125176 KB Output is correct
57 Correct 136 ms 149256 KB Output is correct
58 Correct 70 ms 126740 KB Output is correct
59 Correct 94 ms 128848 KB Output is correct
60 Correct 78 ms 130676 KB Output is correct
61 Correct 77 ms 129832 KB Output is correct
62 Correct 159 ms 157036 KB Output is correct
63 Runtime error 564 ms 262144 KB Execution killed with signal 11
64 Halted 0 ms 0 KB -