oj.uz

Submission #771268

# Submission time Handle Problem Language Result Execution time Memory
771268 2023-07-02T18:44:21 Z IBory Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 477 ms 262144 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 4000000;
vector<int> G[MAX];
bool noL[MAX];
int D[MAX];

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

	int node = N + 1, SN, EN;
	for (auto& [q, v] : make) {
		auto [p, i] = q;
		if (!i) i += p;
		vector<int> fr;
		for (int j = i; j <= N; j += p) {
			if (S == pii{ j, p }) SN = node;
			if (E == pii{ j, p }) EN = node;
			G[node].push_back(-j);
			fr.push_back(node++);
		}
		noL[fr[0]] = noL[fr.back() + 1] = 1;
		for (int n : v) {
			G[n].push_back(-fr[(n - 1) / p]);
		}
	}
	make.clear();
	for (int i = 1; i <= N; ++i) noL[i] = 1;

	memset(D, 0x3f, sizeof(D));
	D[SN] = 0;
	deque<int> Q;
	Q.push_back(SN);
	while (!Q.empty()) {
		int cur = Q.front(); Q.pop_front();
		if (cur == EN) break;
		if (!noL[cur]) G[cur].push_back(cur - 1);
		if (!noL[cur + 1]) G[cur].push_back(cur + 1);

		for (int next : G[cur]) {
			int d = 1;
			if (next < 0) {
				d = 0;
				next *= -1;
			}
			if (D[cur] + d >= D[next]) continue;
			D[next] = D[cur] + d;
			if (d == 0) Q.push_front(next);
			else Q.push_back(next);
		}

		if (!noL[cur]) G[cur].pop_back();
		if (!noL[cur + 1]) G[cur].pop_back();
	}

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

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:29:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |  for (auto& [q, v] : make) {
      |             ^
skyscraper.cpp:30:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |   auto [p, i] = q;
      |        ^
skyscraper.cpp:73:15: warning: 'EN' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |  cout << (D[EN] > 1E9 ? -1 : D[EN]);
      |           ~~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 109796 KB Output is correct
2 Correct 50 ms 109848 KB Output is correct
3 Correct 50 ms 109880 KB Output is correct
4 Correct 49 ms 109772 KB Output is correct
5 Correct 52 ms 109908 KB Output is correct
6 Correct 49 ms 109772 KB Output is correct
7 Correct 50 ms 109808 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 109780 KB Output is correct
2 Correct 50 ms 109896 KB Output is correct
3 Correct 51 ms 109896 KB Output is correct
4 Correct 52 ms 109772 KB Output is correct
5 Correct 53 ms 109800 KB Output is correct
6 Correct 51 ms 109888 KB Output is correct
7 Correct 54 ms 109836 KB Output is correct
8 Correct 52 ms 109896 KB Output is correct
9 Correct 54 ms 109808 KB Output is correct
10 Correct 53 ms 109996 KB Output is correct
11 Correct 58 ms 110284 KB Output is correct
12 Correct 55 ms 109900 KB Output is correct
13 Correct 51 ms 109908 KB Output is correct
14 Correct 54 ms 110284 KB Output is correct
15 Correct 55 ms 110260 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 109856 KB Output is correct
2 Correct 52 ms 109820 KB Output is correct
3 Correct 53 ms 109896 KB Output is correct
4 Correct 53 ms 109836 KB Output is correct
5 Correct 52 ms 109900 KB Output is correct
6 Correct 51 ms 109772 KB Output is correct
7 Correct 50 ms 109896 KB Output is correct
8 Correct 53 ms 109872 KB Output is correct
9 Correct 51 ms 109856 KB Output is correct
10 Correct 52 ms 109928 KB Output is correct
11 Correct 53 ms 110212 KB Output is correct
12 Correct 53 ms 109928 KB Output is correct
13 Correct 52 ms 109928 KB Output is correct
14 Correct 54 ms 110220 KB Output is correct
15 Correct 53 ms 110340 KB Output is correct
16 Correct 53 ms 110004 KB Output is correct
17 Correct 53 ms 110588 KB Output is correct
18 Correct 52 ms 110164 KB Output is correct
19 Correct 51 ms 110028 KB Output is correct
20 Correct 53 ms 109944 KB Output is correct
21 Correct 53 ms 110112 KB Output is correct
22 Correct 52 ms 110168 KB Output is correct
23 Correct 56 ms 110200 KB Output is correct
24 Correct 59 ms 110516 KB Output is correct
25 Correct 53 ms 110404 KB Output is correct
26 Correct 53 ms 110168 KB Output is correct
27 Correct 53 ms 110176 KB Output is correct
28 Correct 54 ms 110876 KB Output is correct
29 Correct 62 ms 111972 KB Output is correct
30 Correct 53 ms 110396 KB Output is correct
31 Correct 53 ms 111052 KB Output is correct
32 Correct 61 ms 110716 KB Output is correct
33 Correct 64 ms 113916 KB Output is correct
34 Correct 62 ms 114100 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 109860 KB Output is correct
2 Correct 51 ms 109856 KB Output is correct
3 Correct 52 ms 109896 KB Output is correct
4 Correct 53 ms 109848 KB Output is correct
5 Correct 54 ms 109888 KB Output is correct
6 Correct 51 ms 109828 KB Output is correct
7 Correct 53 ms 109832 KB Output is correct
8 Correct 52 ms 109848 KB Output is correct
9 Correct 57 ms 109828 KB Output is correct
10 Correct 53 ms 110000 KB Output is correct
11 Correct 53 ms 110224 KB Output is correct
12 Correct 51 ms 109860 KB Output is correct
13 Correct 52 ms 109832 KB Output is correct
14 Correct 54 ms 110332 KB Output is correct
15 Correct 54 ms 110300 KB Output is correct
16 Correct 53 ms 110104 KB Output is correct
17 Correct 54 ms 110580 KB Output is correct
18 Correct 52 ms 110236 KB Output is correct
19 Correct 53 ms 110036 KB Output is correct
20 Correct 62 ms 110028 KB Output is correct
21 Correct 53 ms 110072 KB Output is correct
22 Correct 60 ms 110260 KB Output is correct
23 Correct 53 ms 110188 KB Output is correct
24 Correct 53 ms 110440 KB Output is correct
25 Correct 53 ms 110292 KB Output is correct
26 Correct 54 ms 110064 KB Output is correct
27 Correct 53 ms 110168 KB Output is correct
28 Correct 54 ms 110824 KB Output is correct
29 Correct 60 ms 111968 KB Output is correct
30 Correct 54 ms 110364 KB Output is correct
31 Correct 56 ms 110924 KB Output is correct
32 Correct 55 ms 110696 KB Output is correct
33 Correct 66 ms 114020 KB Output is correct
34 Correct 61 ms 113992 KB Output is correct
35 Correct 74 ms 116172 KB Output is correct
36 Correct 58 ms 111076 KB Output is correct
37 Correct 85 ms 117632 KB Output is correct
38 Correct 80 ms 118476 KB Output is correct
39 Correct 75 ms 118468 KB Output is correct
40 Correct 77 ms 118428 KB Output is correct
41 Correct 77 ms 118440 KB Output is correct
42 Correct 67 ms 110356 KB Output is correct
43 Correct 59 ms 110300 KB Output is correct
44 Correct 57 ms 110284 KB Output is correct
45 Correct 141 ms 128880 KB Output is correct
46 Correct 124 ms 128844 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 109852 KB Output is correct
2 Correct 52 ms 109896 KB Output is correct
3 Correct 58 ms 109832 KB Output is correct
4 Correct 52 ms 109772 KB Output is correct
5 Correct 51 ms 109876 KB Output is correct
6 Correct 52 ms 109892 KB Output is correct
7 Correct 52 ms 109772 KB Output is correct
8 Correct 59 ms 109832 KB Output is correct
9 Correct 53 ms 109900 KB Output is correct
10 Correct 53 ms 109992 KB Output is correct
11 Correct 53 ms 110160 KB Output is correct
12 Correct 53 ms 109824 KB Output is correct
13 Correct 57 ms 109848 KB Output is correct
14 Correct 55 ms 110260 KB Output is correct
15 Correct 53 ms 110284 KB Output is correct
16 Correct 58 ms 110184 KB Output is correct
17 Correct 55 ms 110600 KB Output is correct
18 Correct 56 ms 110148 KB Output is correct
19 Correct 54 ms 110084 KB Output is correct
20 Correct 54 ms 110044 KB Output is correct
21 Correct 52 ms 110124 KB Output is correct
22 Correct 52 ms 110076 KB Output is correct
23 Correct 53 ms 110156 KB Output is correct
24 Correct 55 ms 110548 KB Output is correct
25 Correct 54 ms 110316 KB Output is correct
26 Correct 53 ms 110076 KB Output is correct
27 Correct 55 ms 110168 KB Output is correct
28 Correct 56 ms 110892 KB Output is correct
29 Correct 60 ms 111972 KB Output is correct
30 Correct 55 ms 110408 KB Output is correct
31 Correct 57 ms 111032 KB Output is correct
32 Correct 55 ms 110720 KB Output is correct
33 Correct 65 ms 114008 KB Output is correct
34 Correct 62 ms 113944 KB Output is correct
35 Correct 75 ms 116220 KB Output is correct
36 Correct 55 ms 110952 KB Output is correct
37 Correct 78 ms 117816 KB Output is correct
38 Correct 80 ms 118476 KB Output is correct
39 Correct 74 ms 118452 KB Output is correct
40 Correct 74 ms 118464 KB Output is correct
41 Correct 76 ms 118552 KB Output is correct
42 Correct 56 ms 110320 KB Output is correct
43 Correct 65 ms 110372 KB Output is correct
44 Correct 55 ms 110268 KB Output is correct
45 Correct 136 ms 128876 KB Output is correct
46 Correct 118 ms 128820 KB Output is correct
47 Correct 107 ms 136552 KB Output is correct
48 Correct 72 ms 120292 KB Output is correct
49 Correct 71 ms 117312 KB Output is correct
50 Correct 65 ms 116448 KB Output is correct
51 Correct 94 ms 123936 KB Output is correct
52 Correct 106 ms 124864 KB Output is correct
53 Correct 72 ms 116608 KB Output is correct
54 Correct 54 ms 110864 KB Output is correct
55 Correct 55 ms 111684 KB Output is correct
56 Correct 66 ms 111876 KB Output is correct
57 Correct 69 ms 123940 KB Output is correct
58 Correct 62 ms 112216 KB Output is correct
59 Correct 63 ms 113220 KB Output is correct
60 Correct 71 ms 114172 KB Output is correct
61 Correct 66 ms 113784 KB Output is correct
62 Correct 119 ms 129940 KB Output is correct
63 Correct 423 ms 186960 KB Output is correct
64 Correct 477 ms 203676 KB Output is correct
65 Runtime error 387 ms 262144 KB Execution killed with signal 11
66 Halted 0 ms 0 KB -