oj.uz

Submission #771234

# Submission time Handle Problem Language Result Execution time Memory
771234 2023-07-02T16:57:06 Z IBory Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 551 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) {
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
		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:26:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |   auto [p, i] = q;
      |        ^
skyscraper.cpp:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for (int n = 0; n < fr.size(); ++n) {
      |                   ~~^~~~~~~~~~~
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 + 1 < fr.size()) G[s].push_back(fr[n + 1]);
      |        ~~~~~~^~~~~~~~~~~
skyscraper.cpp:46:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |    if (n + 2 < fr.size()) G[s].push_back(node - 2 * fr.size() + n + 2);
      |        ~~~~~~^~~~~~~~~~~
skyscraper.cpp:64:14: warning: 'E' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |  cout << (D[E] > 1E9 ? -1 : D[E]);
      |           ~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 121988 KB Output is correct
2 Correct 54 ms 122048 KB Output is correct
3 Correct 53 ms 121964 KB Output is correct
4 Correct 56 ms 122016 KB Output is correct
5 Correct 55 ms 122056 KB Output is correct
6 Correct 59 ms 122036 KB Output is correct
7 Correct 56 ms 121980 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 122016 KB Output is correct
2 Correct 56 ms 121944 KB Output is correct
3 Correct 54 ms 122060 KB Output is correct
4 Correct 56 ms 122036 KB Output is correct
5 Correct 55 ms 122056 KB Output is correct
6 Correct 56 ms 122068 KB Output is correct
7 Correct 63 ms 122060 KB Output is correct
8 Correct 56 ms 121956 KB Output is correct
9 Correct 62 ms 121984 KB Output is correct
10 Correct 56 ms 122208 KB Output is correct
11 Correct 58 ms 122444 KB Output is correct
12 Correct 57 ms 122108 KB Output is correct
13 Correct 60 ms 122248 KB Output is correct
14 Correct 58 ms 122648 KB Output is correct
15 Correct 62 ms 122604 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 122004 KB Output is correct
2 Correct 56 ms 122064 KB Output is correct
3 Correct 55 ms 121968 KB Output is correct
4 Correct 58 ms 122064 KB Output is correct
5 Correct 57 ms 121952 KB Output is correct
6 Correct 56 ms 121948 KB Output is correct
7 Correct 56 ms 122060 KB Output is correct
8 Correct 55 ms 122060 KB Output is correct
9 Correct 56 ms 122024 KB Output is correct
10 Correct 56 ms 122148 KB Output is correct
11 Correct 57 ms 122452 KB Output is correct
12 Correct 56 ms 122092 KB Output is correct
13 Correct 56 ms 122068 KB Output is correct
14 Correct 57 ms 122680 KB Output is correct
15 Correct 58 ms 122640 KB Output is correct
16 Correct 58 ms 122308 KB Output is correct
17 Correct 67 ms 123100 KB Output is correct
18 Correct 56 ms 122492 KB Output is correct
19 Correct 58 ms 122352 KB Output is correct
20 Correct 57 ms 122160 KB Output is correct
21 Correct 56 ms 122268 KB Output is correct
22 Correct 67 ms 122416 KB Output is correct
23 Correct 58 ms 122472 KB Output is correct
24 Correct 59 ms 123044 KB Output is correct
25 Correct 58 ms 122796 KB Output is correct
26 Correct 57 ms 122524 KB Output is correct
27 Correct 58 ms 122456 KB Output is correct
28 Correct 59 ms 123724 KB Output is correct
29 Correct 66 ms 125940 KB Output is correct
30 Correct 59 ms 123064 KB Output is correct
31 Correct 62 ms 124184 KB Output is correct
32 Correct 59 ms 123596 KB Output is correct
33 Correct 78 ms 129832 KB Output is correct
34 Correct 77 ms 129812 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 122068 KB Output is correct
2 Correct 56 ms 122064 KB Output is correct
3 Correct 57 ms 121976 KB Output is correct
4 Correct 83 ms 122064 KB Output is correct
5 Correct 56 ms 122000 KB Output is correct
6 Correct 57 ms 122060 KB Output is correct
7 Correct 56 ms 122008 KB Output is correct
8 Correct 58 ms 122060 KB Output is correct
9 Correct 55 ms 122028 KB Output is correct
10 Correct 57 ms 122140 KB Output is correct
11 Correct 57 ms 122512 KB Output is correct
12 Correct 57 ms 122060 KB Output is correct
13 Correct 57 ms 122044 KB Output is correct
14 Correct 59 ms 122572 KB Output is correct
15 Correct 57 ms 122680 KB Output is correct
16 Correct 57 ms 122400 KB Output is correct
17 Correct 59 ms 123172 KB Output is correct
18 Correct 59 ms 122524 KB Output is correct
19 Correct 57 ms 122364 KB Output is correct
20 Correct 64 ms 122188 KB Output is correct
21 Correct 57 ms 122316 KB Output is correct
22 Correct 57 ms 122444 KB Output is correct
23 Correct 57 ms 122600 KB Output is correct
24 Correct 59 ms 123084 KB Output is correct
25 Correct 59 ms 122744 KB Output is correct
26 Correct 58 ms 122480 KB Output is correct
27 Correct 57 ms 122424 KB Output is correct
28 Correct 61 ms 123664 KB Output is correct
29 Correct 68 ms 125992 KB Output is correct
30 Correct 60 ms 123056 KB Output is correct
31 Correct 63 ms 124124 KB Output is correct
32 Correct 61 ms 123508 KB Output is correct
33 Correct 77 ms 129812 KB Output is correct
34 Correct 77 ms 129744 KB Output is correct
35 Correct 87 ms 131344 KB Output is correct
36 Correct 61 ms 123688 KB Output is correct
37 Correct 96 ms 135200 KB Output is correct
38 Correct 101 ms 135596 KB Output is correct
39 Correct 121 ms 135616 KB Output is correct
40 Correct 100 ms 135656 KB Output is correct
41 Correct 101 ms 135612 KB Output is correct
42 Correct 62 ms 122676 KB Output is correct
43 Correct 61 ms 122644 KB Output is correct
44 Correct 61 ms 122316 KB Output is correct
45 Correct 159 ms 155768 KB Output is correct
46 Correct 157 ms 155816 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 122060 KB Output is correct
2 Correct 57 ms 122016 KB Output is correct
3 Correct 56 ms 122064 KB Output is correct
4 Correct 58 ms 122040 KB Output is correct
5 Correct 57 ms 122060 KB Output is correct
6 Correct 57 ms 122040 KB Output is correct
7 Correct 57 ms 121944 KB Output is correct
8 Correct 57 ms 122020 KB Output is correct
9 Correct 57 ms 122000 KB Output is correct
10 Correct 57 ms 122208 KB Output is correct
11 Correct 58 ms 122524 KB Output is correct
12 Correct 57 ms 122068 KB Output is correct
13 Correct 57 ms 122092 KB Output is correct
14 Correct 59 ms 122612 KB Output is correct
15 Correct 58 ms 122600 KB Output is correct
16 Correct 56 ms 122348 KB Output is correct
17 Correct 59 ms 123084 KB Output is correct
18 Correct 58 ms 122584 KB Output is correct
19 Correct 58 ms 122316 KB Output is correct
20 Correct 57 ms 122240 KB Output is correct
21 Correct 57 ms 122448 KB Output is correct
22 Correct 58 ms 122516 KB Output is correct
23 Correct 59 ms 122488 KB Output is correct
24 Correct 60 ms 123084 KB Output is correct
25 Correct 60 ms 122716 KB Output is correct
26 Correct 59 ms 122448 KB Output is correct
27 Correct 63 ms 122608 KB Output is correct
28 Correct 64 ms 123724 KB Output is correct
29 Correct 66 ms 125936 KB Output is correct
30 Correct 60 ms 123172 KB Output is correct
31 Correct 62 ms 124220 KB Output is correct
32 Correct 59 ms 123564 KB Output is correct
33 Correct 79 ms 129768 KB Output is correct
34 Correct 79 ms 129812 KB Output is correct
35 Correct 84 ms 131368 KB Output is correct
36 Correct 56 ms 123724 KB Output is correct
37 Correct 95 ms 135164 KB Output is correct
38 Correct 95 ms 135580 KB Output is correct
39 Correct 100 ms 135628 KB Output is correct
40 Correct 95 ms 135540 KB Output is correct
41 Correct 95 ms 135580 KB Output is correct
42 Correct 53 ms 122680 KB Output is correct
43 Correct 53 ms 122600 KB Output is correct
44 Correct 61 ms 122388 KB Output is correct
45 Correct 166 ms 155860 KB Output is correct
46 Correct 157 ms 155724 KB Output is correct
47 Correct 204 ms 171336 KB Output is correct
48 Correct 108 ms 139528 KB Output is correct
49 Correct 93 ms 133712 KB Output is correct
50 Correct 86 ms 132948 KB Output is correct
51 Correct 139 ms 145704 KB Output is correct
52 Correct 133 ms 147544 KB Output is correct
53 Correct 85 ms 131040 KB Output is correct
54 Correct 62 ms 123988 KB Output is correct
55 Correct 62 ms 125544 KB Output is correct
56 Correct 68 ms 125020 KB Output is correct
57 Correct 138 ms 149188 KB Output is correct
58 Correct 67 ms 126304 KB Output is correct
59 Correct 73 ms 128156 KB Output is correct
60 Correct 76 ms 129912 KB Output is correct
61 Correct 79 ms 129152 KB Output is correct
62 Correct 148 ms 156644 KB Output is correct
63 Runtime error 551 ms 262144 KB Execution killed with signal 11
64 Halted 0 ms 0 KB -