oj.uz

답안 #771256

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

const int MAX = 5000005;
vector<int> G[MAX];
vector<int> C[30003];
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;
			C[j].push_back(node);
			fr.push_back(node++);
		}
		for (int j = 1; j < fr.size(); ++j) {
			G[fr[j - 1]].emplace_back(fr[j]);
			G[fr[j]].emplace_back(fr[j - 1]);
		}
		for (int n : v) {
			G[n].push_back(-fr[(n - 1) / p]);
		}
	}
	make.clear();
	
	for (int i = 1; i <= N; ++i) {
		for (int n : C[i]) {
			G[n].push_back(-i);
		}
		C[i].clear();
	}

	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();
		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);
		}
	}

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

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:25:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |  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:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int j = 1; j < fr.size(); ++j) {
      |                   ~~^~~~~~~~~~~
skyscraper.cpp:71:15: warning: 'EN' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |  cout << (D[EN] > 1E9 ? -1 : D[EN]);
      |           ~~~~^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 137932 KB Output is correct
2 Correct 67 ms 137908 KB Output is correct
3 Correct 58 ms 137996 KB Output is correct
4 Correct 56 ms 137968 KB Output is correct
5 Correct 55 ms 137932 KB Output is correct
6 Correct 62 ms 137872 KB Output is correct
7 Correct 60 ms 137936 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 137932 KB Output is correct
2 Correct 57 ms 137952 KB Output is correct
3 Correct 64 ms 137948 KB Output is correct
4 Correct 58 ms 137904 KB Output is correct
5 Correct 58 ms 137920 KB Output is correct
6 Correct 61 ms 137996 KB Output is correct
7 Correct 57 ms 137884 KB Output is correct
8 Correct 59 ms 137900 KB Output is correct
9 Correct 59 ms 138016 KB Output is correct
10 Correct 60 ms 138056 KB Output is correct
11 Correct 71 ms 138264 KB Output is correct
12 Correct 60 ms 137940 KB Output is correct
13 Correct 59 ms 137932 KB Output is correct
14 Correct 60 ms 138468 KB Output is correct
15 Correct 62 ms 138428 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 137972 KB Output is correct
2 Correct 66 ms 138000 KB Output is correct
3 Correct 64 ms 137932 KB Output is correct
4 Correct 61 ms 138012 KB Output is correct
5 Correct 59 ms 137932 KB Output is correct
6 Correct 59 ms 137980 KB Output is correct
7 Correct 58 ms 137996 KB Output is correct
8 Correct 57 ms 138004 KB Output is correct
9 Correct 57 ms 137932 KB Output is correct
10 Correct 63 ms 138108 KB Output is correct
11 Correct 60 ms 138316 KB Output is correct
12 Correct 63 ms 138040 KB Output is correct
13 Correct 61 ms 137940 KB Output is correct
14 Correct 60 ms 138344 KB Output is correct
15 Correct 62 ms 138460 KB Output is correct
16 Correct 59 ms 138168 KB Output is correct
17 Correct 70 ms 138864 KB Output is correct
18 Correct 60 ms 138440 KB Output is correct
19 Correct 61 ms 138264 KB Output is correct
20 Correct 58 ms 138112 KB Output is correct
21 Correct 59 ms 138164 KB Output is correct
22 Correct 59 ms 138276 KB Output is correct
23 Correct 59 ms 138388 KB Output is correct
24 Correct 63 ms 138692 KB Output is correct
25 Correct 61 ms 138464 KB Output is correct
26 Correct 60 ms 138316 KB Output is correct
27 Correct 61 ms 138284 KB Output is correct
28 Correct 74 ms 139080 KB Output is correct
29 Correct 69 ms 140448 KB Output is correct
30 Correct 62 ms 138756 KB Output is correct
31 Correct 64 ms 139364 KB Output is correct
32 Correct 62 ms 138952 KB Output is correct
33 Correct 80 ms 142504 KB Output is correct
34 Correct 78 ms 142544 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 138000 KB Output is correct
2 Correct 58 ms 137992 KB Output is correct
3 Correct 57 ms 137980 KB Output is correct
4 Correct 57 ms 137884 KB Output is correct
5 Correct 59 ms 137988 KB Output is correct
6 Correct 59 ms 137916 KB Output is correct
7 Correct 59 ms 137940 KB Output is correct
8 Correct 67 ms 137932 KB Output is correct
9 Correct 65 ms 138288 KB Output is correct
10 Correct 60 ms 138060 KB Output is correct
11 Correct 62 ms 138220 KB Output is correct
12 Correct 59 ms 137900 KB Output is correct
13 Correct 60 ms 137968 KB Output is correct
14 Correct 60 ms 138396 KB Output is correct
15 Correct 61 ms 138384 KB Output is correct
16 Correct 61 ms 138128 KB Output is correct
17 Correct 61 ms 138676 KB Output is correct
18 Correct 69 ms 138368 KB Output is correct
19 Correct 60 ms 138240 KB Output is correct
20 Correct 64 ms 138188 KB Output is correct
21 Correct 60 ms 138188 KB Output is correct
22 Correct 61 ms 138316 KB Output is correct
23 Correct 63 ms 138316 KB Output is correct
24 Correct 62 ms 138636 KB Output is correct
25 Correct 62 ms 138516 KB Output is correct
26 Correct 59 ms 138340 KB Output is correct
27 Correct 61 ms 138272 KB Output is correct
28 Correct 73 ms 139084 KB Output is correct
29 Correct 69 ms 140320 KB Output is correct
30 Correct 62 ms 138676 KB Output is correct
31 Correct 63 ms 139360 KB Output is correct
32 Correct 72 ms 138836 KB Output is correct
33 Correct 85 ms 142596 KB Output is correct
34 Correct 81 ms 142560 KB Output is correct
35 Correct 94 ms 144528 KB Output is correct
36 Correct 72 ms 139084 KB Output is correct
37 Correct 107 ms 146612 KB Output is correct
38 Correct 109 ms 147376 KB Output is correct
39 Correct 111 ms 147344 KB Output is correct
40 Correct 118 ms 147280 KB Output is correct
41 Correct 117 ms 147380 KB Output is correct
42 Correct 69 ms 138464 KB Output is correct
43 Correct 70 ms 138548 KB Output is correct
44 Correct 64 ms 138488 KB Output is correct
45 Correct 182 ms 158656 KB Output is correct
46 Correct 197 ms 158672 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 137892 KB Output is correct
2 Correct 59 ms 137992 KB Output is correct
3 Correct 59 ms 137992 KB Output is correct
4 Correct 58 ms 137948 KB Output is correct
5 Correct 62 ms 137972 KB Output is correct
6 Correct 61 ms 138032 KB Output is correct
7 Correct 58 ms 137932 KB Output is correct
8 Correct 65 ms 137992 KB Output is correct
9 Correct 68 ms 137900 KB Output is correct
10 Correct 62 ms 138000 KB Output is correct
11 Correct 59 ms 138288 KB Output is correct
12 Correct 61 ms 138044 KB Output is correct
13 Correct 59 ms 138016 KB Output is correct
14 Correct 61 ms 138356 KB Output is correct
15 Correct 63 ms 138380 KB Output is correct
16 Correct 60 ms 138220 KB Output is correct
17 Correct 62 ms 138728 KB Output is correct
18 Correct 61 ms 138344 KB Output is correct
19 Correct 62 ms 138212 KB Output is correct
20 Correct 59 ms 138204 KB Output is correct
21 Correct 59 ms 138188 KB Output is correct
22 Correct 60 ms 138204 KB Output is correct
23 Correct 59 ms 138316 KB Output is correct
24 Correct 62 ms 138616 KB Output is correct
25 Correct 60 ms 138432 KB Output is correct
26 Correct 66 ms 138392 KB Output is correct
27 Correct 63 ms 138260 KB Output is correct
28 Correct 65 ms 139052 KB Output is correct
29 Correct 68 ms 140236 KB Output is correct
30 Correct 64 ms 138700 KB Output is correct
31 Correct 63 ms 139340 KB Output is correct
32 Correct 62 ms 138896 KB Output is correct
33 Correct 78 ms 142484 KB Output is correct
34 Correct 79 ms 142592 KB Output is correct
35 Correct 93 ms 144588 KB Output is correct
36 Correct 64 ms 139172 KB Output is correct
37 Correct 101 ms 146576 KB Output is correct
38 Correct 124 ms 147276 KB Output is correct
39 Correct 108 ms 147328 KB Output is correct
40 Correct 107 ms 147388 KB Output is correct
41 Correct 111 ms 147392 KB Output is correct
42 Correct 65 ms 138500 KB Output is correct
43 Correct 65 ms 138516 KB Output is correct
44 Correct 63 ms 138444 KB Output is correct
45 Correct 168 ms 158676 KB Output is correct
46 Correct 169 ms 158624 KB Output is correct
47 Correct 285 ms 168544 KB Output is correct
48 Correct 118 ms 149728 KB Output is correct
49 Correct 96 ms 146104 KB Output is correct
50 Correct 91 ms 145552 KB Output is correct
51 Correct 162 ms 153844 KB Output is correct
52 Correct 171 ms 154952 KB Output is correct
53 Correct 94 ms 144860 KB Output is correct
54 Correct 61 ms 139932 KB Output is correct
55 Correct 66 ms 140696 KB Output is correct
56 Correct 67 ms 140860 KB Output is correct
57 Correct 159 ms 154452 KB Output is correct
58 Correct 71 ms 141332 KB Output is correct
59 Correct 86 ms 142260 KB Output is correct
60 Correct 86 ms 143280 KB Output is correct
61 Correct 85 ms 142824 KB Output is correct
62 Correct 202 ms 160840 KB Output is correct
63 Correct 758 ms 229444 KB Output is correct
64 Correct 775 ms 246176 KB Output is correct
65 Runtime error 347 ms 262144 KB Execution killed with signal 9
66 Halted 0 ms 0 KB -