oj.uz

답안 #771254

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

const int MAX = 5555555;
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]);
		}
	}
	
	for (int i = 1; i <= N; ++i) {
		for (int n : C[i]) {
			G[n].push_back(-i);
		}
	}

	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:69:15: warning: 'EN' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |  cout << (D[EN] > 1E9 ? -1 : D[EN]);
      |           ~~~~^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 153192 KB Output is correct
2 Correct 59 ms 153092 KB Output is correct
3 Correct 58 ms 153092 KB Output is correct
4 Correct 59 ms 153144 KB Output is correct
5 Correct 57 ms 153136 KB Output is correct
6 Correct 58 ms 153096 KB Output is correct
7 Correct 59 ms 153176 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 153184 KB Output is correct
2 Correct 59 ms 153268 KB Output is correct
3 Correct 74 ms 153096 KB Output is correct
4 Correct 59 ms 153112 KB Output is correct
5 Correct 60 ms 153212 KB Output is correct
6 Correct 60 ms 153184 KB Output is correct
7 Correct 58 ms 153104 KB Output is correct
8 Correct 58 ms 153100 KB Output is correct
9 Correct 58 ms 153220 KB Output is correct
10 Correct 59 ms 153312 KB Output is correct
11 Correct 59 ms 153528 KB Output is correct
12 Correct 64 ms 153160 KB Output is correct
13 Correct 58 ms 153160 KB Output is correct
14 Correct 59 ms 153672 KB Output is correct
15 Correct 61 ms 153632 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 153112 KB Output is correct
2 Correct 59 ms 153204 KB Output is correct
3 Correct 60 ms 153168 KB Output is correct
4 Correct 60 ms 153160 KB Output is correct
5 Correct 58 ms 153108 KB Output is correct
6 Correct 59 ms 153204 KB Output is correct
7 Correct 59 ms 153160 KB Output is correct
8 Correct 59 ms 153164 KB Output is correct
9 Correct 59 ms 153164 KB Output is correct
10 Correct 60 ms 153192 KB Output is correct
11 Correct 59 ms 153536 KB Output is correct
12 Correct 59 ms 153248 KB Output is correct
13 Correct 59 ms 153240 KB Output is correct
14 Correct 62 ms 153676 KB Output is correct
15 Correct 59 ms 153640 KB Output is correct
16 Correct 60 ms 153420 KB Output is correct
17 Correct 63 ms 153916 KB Output is correct
18 Correct 60 ms 153548 KB Output is correct
19 Correct 60 ms 153404 KB Output is correct
20 Correct 60 ms 153392 KB Output is correct
21 Correct 61 ms 153404 KB Output is correct
22 Correct 69 ms 153548 KB Output is correct
23 Correct 61 ms 153604 KB Output is correct
24 Correct 62 ms 153880 KB Output is correct
25 Correct 61 ms 153772 KB Output is correct
26 Correct 61 ms 153516 KB Output is correct
27 Correct 59 ms 153440 KB Output is correct
28 Correct 65 ms 154372 KB Output is correct
29 Correct 71 ms 155496 KB Output is correct
30 Correct 61 ms 153852 KB Output is correct
31 Correct 65 ms 154564 KB Output is correct
32 Correct 62 ms 154144 KB Output is correct
33 Correct 78 ms 157804 KB Output is correct
34 Correct 77 ms 157816 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 153184 KB Output is correct
2 Correct 90 ms 153212 KB Output is correct
3 Correct 71 ms 153156 KB Output is correct
4 Correct 87 ms 153120 KB Output is correct
5 Correct 69 ms 153180 KB Output is correct
6 Correct 67 ms 153164 KB Output is correct
7 Correct 71 ms 153396 KB Output is correct
8 Correct 69 ms 153108 KB Output is correct
9 Correct 68 ms 153164 KB Output is correct
10 Correct 69 ms 153204 KB Output is correct
11 Correct 69 ms 153568 KB Output is correct
12 Correct 69 ms 153232 KB Output is correct
13 Correct 76 ms 153372 KB Output is correct
14 Correct 70 ms 153576 KB Output is correct
15 Correct 70 ms 153624 KB Output is correct
16 Correct 70 ms 153420 KB Output is correct
17 Correct 70 ms 154020 KB Output is correct
18 Correct 69 ms 153636 KB Output is correct
19 Correct 69 ms 153504 KB Output is correct
20 Correct 67 ms 153428 KB Output is correct
21 Correct 68 ms 153420 KB Output is correct
22 Correct 68 ms 153500 KB Output is correct
23 Correct 68 ms 153596 KB Output is correct
24 Correct 70 ms 153948 KB Output is correct
25 Correct 79 ms 153784 KB Output is correct
26 Correct 68 ms 153516 KB Output is correct
27 Correct 67 ms 153548 KB Output is correct
28 Correct 70 ms 154372 KB Output is correct
29 Correct 77 ms 155536 KB Output is correct
30 Correct 69 ms 153964 KB Output is correct
31 Correct 79 ms 154632 KB Output is correct
32 Correct 72 ms 154104 KB Output is correct
33 Correct 89 ms 157712 KB Output is correct
34 Correct 86 ms 157776 KB Output is correct
35 Correct 103 ms 160304 KB Output is correct
36 Correct 76 ms 154500 KB Output is correct
37 Correct 137 ms 162124 KB Output is correct
38 Correct 114 ms 163004 KB Output is correct
39 Correct 115 ms 162956 KB Output is correct
40 Correct 132 ms 162984 KB Output is correct
41 Correct 114 ms 162944 KB Output is correct
42 Correct 74 ms 153852 KB Output is correct
43 Correct 72 ms 153892 KB Output is correct
44 Correct 71 ms 153748 KB Output is correct
45 Correct 247 ms 174196 KB Output is correct
46 Correct 209 ms 174092 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 153112 KB Output is correct
2 Correct 67 ms 153120 KB Output is correct
3 Correct 69 ms 153164 KB Output is correct
4 Correct 67 ms 153232 KB Output is correct
5 Correct 68 ms 153088 KB Output is correct
6 Correct 67 ms 153164 KB Output is correct
7 Correct 67 ms 153164 KB Output is correct
8 Correct 69 ms 153112 KB Output is correct
9 Correct 72 ms 153260 KB Output is correct
10 Correct 69 ms 153208 KB Output is correct
11 Correct 69 ms 153480 KB Output is correct
12 Correct 68 ms 153152 KB Output is correct
13 Correct 68 ms 153252 KB Output is correct
14 Correct 68 ms 153676 KB Output is correct
15 Correct 67 ms 153684 KB Output is correct
16 Correct 65 ms 153464 KB Output is correct
17 Correct 75 ms 153988 KB Output is correct
18 Correct 69 ms 153524 KB Output is correct
19 Correct 70 ms 153504 KB Output is correct
20 Correct 68 ms 153436 KB Output is correct
21 Correct 71 ms 153400 KB Output is correct
22 Correct 70 ms 153532 KB Output is correct
23 Correct 69 ms 153612 KB Output is correct
24 Correct 69 ms 153932 KB Output is correct
25 Correct 69 ms 153756 KB Output is correct
26 Correct 69 ms 153524 KB Output is correct
27 Correct 68 ms 153508 KB Output is correct
28 Correct 72 ms 154380 KB Output is correct
29 Correct 77 ms 155528 KB Output is correct
30 Correct 69 ms 153916 KB Output is correct
31 Correct 72 ms 154596 KB Output is correct
32 Correct 70 ms 154120 KB Output is correct
33 Correct 91 ms 157764 KB Output is correct
34 Correct 95 ms 157764 KB Output is correct
35 Correct 114 ms 160288 KB Output is correct
36 Correct 73 ms 154460 KB Output is correct
37 Correct 108 ms 162124 KB Output is correct
38 Correct 118 ms 162960 KB Output is correct
39 Correct 126 ms 162964 KB Output is correct
40 Correct 133 ms 163028 KB Output is correct
41 Correct 112 ms 162944 KB Output is correct
42 Correct 71 ms 153804 KB Output is correct
43 Correct 70 ms 153804 KB Output is correct
44 Correct 71 ms 154000 KB Output is correct
45 Correct 177 ms 174136 KB Output is correct
46 Correct 209 ms 174156 KB Output is correct
47 Correct 274 ms 184152 KB Output is correct
48 Correct 129 ms 165264 KB Output is correct
49 Correct 108 ms 161728 KB Output is correct
50 Correct 99 ms 160964 KB Output is correct
51 Correct 194 ms 169580 KB Output is correct
52 Correct 176 ms 170712 KB Output is correct
53 Correct 103 ms 161020 KB Output is correct
54 Correct 82 ms 155088 KB Output is correct
55 Correct 77 ms 155932 KB Output is correct
56 Correct 77 ms 156220 KB Output is correct
57 Correct 149 ms 169640 KB Output is correct
58 Correct 92 ms 156544 KB Output is correct
59 Correct 89 ms 157596 KB Output is correct
60 Correct 99 ms 158728 KB Output is correct
61 Correct 91 ms 158348 KB Output is correct
62 Correct 198 ms 176556 KB Output is correct
63 Correct 677 ms 245012 KB Output is correct
64 Correct 839 ms 261816 KB Output is correct
65 Runtime error 324 ms 262144 KB Execution killed with signal 9
66 Halted 0 ms 0 KB -