oj.uz

Submission #745316

# Submission time Handle Problem Language Result Execution time Memory
745316 2023-05-19T20:25:48 Z IBory Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 623 ms 262144 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 4444444;
unordered_map<int, int> mv[33333];
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);
		}
	}

	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:24:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |  for (auto& [q, v] : make) {
      |             ^
skyscraper.cpp:25:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |   auto [p, i] = q;
      |        ^
skyscraper.cpp:29:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for (int n = 0; n < fr.size(); ++n) {
      |                   ~~^~~~~~~~~~~
skyscraper.cpp:43:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    if (n + 1 < fr.size()) G[s].push_back(fr[n + 1]);
      |        ~~~~~~^~~~~~~~~~~
skyscraper.cpp:45:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    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 57 ms 123892 KB Output is correct
2 Correct 59 ms 123984 KB Output is correct
3 Correct 57 ms 123796 KB Output is correct
4 Correct 58 ms 123856 KB Output is correct
5 Correct 58 ms 123852 KB Output is correct
6 Correct 62 ms 123824 KB Output is correct
7 Correct 58 ms 123776 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 123816 KB Output is correct
2 Correct 59 ms 123796 KB Output is correct
3 Correct 57 ms 123792 KB Output is correct
4 Correct 61 ms 123852 KB Output is correct
5 Correct 66 ms 123836 KB Output is correct
6 Correct 59 ms 123856 KB Output is correct
7 Correct 63 ms 123880 KB Output is correct
8 Correct 58 ms 123788 KB Output is correct
9 Correct 58 ms 123900 KB Output is correct
10 Correct 60 ms 124040 KB Output is correct
11 Correct 59 ms 124328 KB Output is correct
12 Correct 58 ms 123948 KB Output is correct
13 Correct 60 ms 123892 KB Output is correct
14 Correct 62 ms 124492 KB Output is correct
15 Correct 61 ms 124484 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 123812 KB Output is correct
2 Correct 58 ms 123856 KB Output is correct
3 Correct 58 ms 123872 KB Output is correct
4 Correct 60 ms 123884 KB Output is correct
5 Correct 59 ms 123852 KB Output is correct
6 Correct 59 ms 123828 KB Output is correct
7 Correct 58 ms 123852 KB Output is correct
8 Correct 58 ms 123840 KB Output is correct
9 Correct 60 ms 123824 KB Output is correct
10 Correct 61 ms 124124 KB Output is correct
11 Correct 60 ms 124324 KB Output is correct
12 Correct 64 ms 123852 KB Output is correct
13 Correct 59 ms 123972 KB Output is correct
14 Correct 61 ms 124444 KB Output is correct
15 Correct 60 ms 124492 KB Output is correct
16 Correct 62 ms 124108 KB Output is correct
17 Correct 63 ms 125000 KB Output is correct
18 Correct 61 ms 124424 KB Output is correct
19 Correct 60 ms 124324 KB Output is correct
20 Correct 67 ms 124156 KB Output is correct
21 Correct 60 ms 124104 KB Output is correct
22 Correct 61 ms 124260 KB Output is correct
23 Correct 60 ms 124364 KB Output is correct
24 Correct 62 ms 124884 KB Output is correct
25 Correct 60 ms 124620 KB Output is correct
26 Correct 63 ms 124320 KB Output is correct
27 Correct 60 ms 124360 KB Output is correct
28 Correct 63 ms 125516 KB Output is correct
29 Correct 74 ms 127820 KB Output is correct
30 Correct 61 ms 124916 KB Output is correct
31 Correct 68 ms 126048 KB Output is correct
32 Correct 63 ms 125328 KB Output is correct
33 Correct 90 ms 131684 KB Output is correct
34 Correct 83 ms 131600 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 123880 KB Output is correct
2 Correct 58 ms 123888 KB Output is correct
3 Correct 64 ms 123832 KB Output is correct
4 Correct 60 ms 123896 KB Output is correct
5 Correct 57 ms 123804 KB Output is correct
6 Correct 60 ms 123852 KB Output is correct
7 Correct 60 ms 123852 KB Output is correct
8 Correct 73 ms 123852 KB Output is correct
9 Correct 60 ms 123864 KB Output is correct
10 Correct 61 ms 123992 KB Output is correct
11 Correct 61 ms 124356 KB Output is correct
12 Correct 62 ms 124028 KB Output is correct
13 Correct 60 ms 123940 KB Output is correct
14 Correct 62 ms 124436 KB Output is correct
15 Correct 65 ms 124516 KB Output is correct
16 Correct 60 ms 124232 KB Output is correct
17 Correct 64 ms 125000 KB Output is correct
18 Correct 61 ms 124364 KB Output is correct
19 Correct 61 ms 124272 KB Output is correct
20 Correct 58 ms 123980 KB Output is correct
21 Correct 60 ms 124120 KB Output is correct
22 Correct 61 ms 124300 KB Output is correct
23 Correct 62 ms 124420 KB Output is correct
24 Correct 62 ms 124852 KB Output is correct
25 Correct 65 ms 124604 KB Output is correct
26 Correct 63 ms 124320 KB Output is correct
27 Correct 67 ms 124352 KB Output is correct
28 Correct 68 ms 125516 KB Output is correct
29 Correct 72 ms 127760 KB Output is correct
30 Correct 62 ms 124996 KB Output is correct
31 Correct 67 ms 126048 KB Output is correct
32 Correct 63 ms 125348 KB Output is correct
33 Correct 87 ms 131572 KB Output is correct
34 Correct 87 ms 131640 KB Output is correct
35 Correct 94 ms 133300 KB Output is correct
36 Correct 64 ms 125584 KB Output is correct
37 Correct 113 ms 137172 KB Output is correct
38 Correct 115 ms 137500 KB Output is correct
39 Correct 109 ms 137540 KB Output is correct
40 Correct 111 ms 137424 KB Output is correct
41 Correct 114 ms 137488 KB Output is correct
42 Correct 65 ms 124868 KB Output is correct
43 Correct 73 ms 124828 KB Output is correct
44 Correct 63 ms 124596 KB Output is correct
45 Correct 216 ms 157824 KB Output is correct
46 Correct 214 ms 157672 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 123844 KB Output is correct
2 Correct 61 ms 123888 KB Output is correct
3 Correct 65 ms 123880 KB Output is correct
4 Correct 59 ms 123772 KB Output is correct
5 Correct 60 ms 123940 KB Output is correct
6 Correct 61 ms 123936 KB Output is correct
7 Correct 61 ms 123848 KB Output is correct
8 Correct 59 ms 123904 KB Output is correct
9 Correct 58 ms 123900 KB Output is correct
10 Correct 61 ms 124000 KB Output is correct
11 Correct 62 ms 124312 KB Output is correct
12 Correct 59 ms 123908 KB Output is correct
13 Correct 61 ms 123844 KB Output is correct
14 Correct 61 ms 124420 KB Output is correct
15 Correct 62 ms 124388 KB Output is correct
16 Correct 63 ms 124312 KB Output is correct
17 Correct 65 ms 124932 KB Output is correct
18 Correct 61 ms 124364 KB Output is correct
19 Correct 61 ms 124236 KB Output is correct
20 Correct 60 ms 123980 KB Output is correct
21 Correct 67 ms 124124 KB Output is correct
22 Correct 61 ms 124324 KB Output is correct
23 Correct 61 ms 124356 KB Output is correct
24 Correct 65 ms 124876 KB Output is correct
25 Correct 65 ms 124568 KB Output is correct
26 Correct 61 ms 124492 KB Output is correct
27 Correct 63 ms 124360 KB Output is correct
28 Correct 67 ms 125500 KB Output is correct
29 Correct 73 ms 127708 KB Output is correct
30 Correct 63 ms 124936 KB Output is correct
31 Correct 66 ms 125988 KB Output is correct
32 Correct 66 ms 125360 KB Output is correct
33 Correct 84 ms 131660 KB Output is correct
34 Correct 87 ms 131652 KB Output is correct
35 Correct 109 ms 133240 KB Output is correct
36 Correct 66 ms 125468 KB Output is correct
37 Correct 114 ms 137200 KB Output is correct
38 Correct 112 ms 137548 KB Output is correct
39 Correct 112 ms 137456 KB Output is correct
40 Correct 112 ms 137420 KB Output is correct
41 Correct 116 ms 137504 KB Output is correct
42 Correct 66 ms 124900 KB Output is correct
43 Correct 68 ms 124908 KB Output is correct
44 Correct 65 ms 124496 KB Output is correct
45 Correct 207 ms 157748 KB Output is correct
46 Correct 209 ms 157744 KB Output is correct
47 Correct 267 ms 173412 KB Output is correct
48 Correct 113 ms 141632 KB Output is correct
49 Correct 96 ms 135788 KB Output is correct
50 Correct 92 ms 134900 KB Output is correct
51 Correct 148 ms 147916 KB Output is correct
52 Correct 160 ms 149624 KB Output is correct
53 Correct 99 ms 133340 KB Output is correct
54 Correct 65 ms 125772 KB Output is correct
55 Correct 74 ms 127376 KB Output is correct
56 Correct 73 ms 127076 KB Output is correct
57 Correct 180 ms 151064 KB Output is correct
58 Correct 77 ms 128632 KB Output is correct
59 Correct 86 ms 130712 KB Output is correct
60 Correct 89 ms 132420 KB Output is correct
61 Correct 86 ms 131744 KB Output is correct
62 Correct 173 ms 158796 KB Output is correct
63 Runtime error 623 ms 262144 KB Execution killed with signal 11
64 Halted 0 ms 0 KB -