oj.uz

답안 #771261

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
771261 2023-07-02T18:25:08 Z IBory Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 1000 ms 258308 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 = 5555555;
vector<int> G[MAX];
vector<int> C[30003];
bitset<MAX> noL, noR;
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++);
		}
		noL[fr[0]] = noR[fr.back()] = 1;
		for (int n : v) {
			G[n].push_back(-fr[(n - 1) / p]);
		}
	}
	make.clear();
	
	for (int i = 1; i <= N; ++i) {
		noL[i] = noR[i] = 1;
		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();
		if (!noL[cur]) G[cur].push_back(cur - 1);
		if (!noR[cur]) 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 (!noR[cur]) G[cur].pop_back();
	}

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

Compilation message

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 153160 KB Output is correct
2 Correct 68 ms 153176 KB Output is correct
3 Correct 70 ms 153176 KB Output is correct
4 Correct 70 ms 153224 KB Output is correct
5 Correct 71 ms 153224 KB Output is correct
6 Correct 68 ms 153132 KB Output is correct
7 Correct 69 ms 153164 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 153204 KB Output is correct
2 Correct 69 ms 153224 KB Output is correct
3 Correct 71 ms 153188 KB Output is correct
4 Correct 82 ms 153208 KB Output is correct
5 Correct 71 ms 153164 KB Output is correct
6 Correct 71 ms 153220 KB Output is correct
7 Correct 70 ms 153180 KB Output is correct
8 Correct 76 ms 153204 KB Output is correct
9 Correct 70 ms 153240 KB Output is correct
10 Correct 72 ms 153328 KB Output is correct
11 Correct 74 ms 153420 KB Output is correct
12 Correct 73 ms 153248 KB Output is correct
13 Correct 79 ms 153188 KB Output is correct
14 Correct 72 ms 153504 KB Output is correct
15 Correct 76 ms 153608 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 153156 KB Output is correct
2 Correct 70 ms 153164 KB Output is correct
3 Correct 70 ms 153172 KB Output is correct
4 Correct 75 ms 153228 KB Output is correct
5 Correct 70 ms 153108 KB Output is correct
6 Correct 71 ms 153164 KB Output is correct
7 Correct 70 ms 153204 KB Output is correct
8 Correct 70 ms 153168 KB Output is correct
9 Correct 70 ms 153188 KB Output is correct
10 Correct 70 ms 153328 KB Output is correct
11 Correct 72 ms 153428 KB Output is correct
12 Correct 72 ms 153160 KB Output is correct
13 Correct 72 ms 153252 KB Output is correct
14 Correct 76 ms 153548 KB Output is correct
15 Correct 81 ms 153564 KB Output is correct
16 Correct 73 ms 153344 KB Output is correct
17 Correct 74 ms 153868 KB Output is correct
18 Correct 72 ms 153472 KB Output is correct
19 Correct 72 ms 153380 KB Output is correct
20 Correct 71 ms 153432 KB Output is correct
21 Correct 72 ms 153436 KB Output is correct
22 Correct 71 ms 153504 KB Output is correct
23 Correct 75 ms 153504 KB Output is correct
24 Correct 84 ms 153852 KB Output is correct
25 Correct 72 ms 153616 KB Output is correct
26 Correct 72 ms 153552 KB Output is correct
27 Correct 72 ms 153484 KB Output is correct
28 Correct 87 ms 154272 KB Output is correct
29 Correct 82 ms 155496 KB Output is correct
30 Correct 75 ms 153916 KB Output is correct
31 Correct 76 ms 154564 KB Output is correct
32 Correct 73 ms 154136 KB Output is correct
33 Correct 95 ms 157664 KB Output is correct
34 Correct 104 ms 157688 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 153124 KB Output is correct
2 Correct 70 ms 153124 KB Output is correct
3 Correct 69 ms 153160 KB Output is correct
4 Correct 69 ms 153116 KB Output is correct
5 Correct 71 ms 153112 KB Output is correct
6 Correct 68 ms 153192 KB Output is correct
7 Correct 70 ms 153108 KB Output is correct
8 Correct 68 ms 153240 KB Output is correct
9 Correct 69 ms 153196 KB Output is correct
10 Correct 71 ms 153328 KB Output is correct
11 Correct 70 ms 153388 KB Output is correct
12 Correct 70 ms 153252 KB Output is correct
13 Correct 69 ms 153216 KB Output is correct
14 Correct 72 ms 153512 KB Output is correct
15 Correct 72 ms 153608 KB Output is correct
16 Correct 69 ms 153432 KB Output is correct
17 Correct 74 ms 153748 KB Output is correct
18 Correct 79 ms 153600 KB Output is correct
19 Correct 81 ms 153468 KB Output is correct
20 Correct 73 ms 153380 KB Output is correct
21 Correct 71 ms 153404 KB Output is correct
22 Correct 71 ms 153452 KB Output is correct
23 Correct 70 ms 153528 KB Output is correct
24 Correct 77 ms 153916 KB Output is correct
25 Correct 73 ms 153688 KB Output is correct
26 Correct 72 ms 153524 KB Output is correct
27 Correct 71 ms 153444 KB Output is correct
28 Correct 75 ms 154272 KB Output is correct
29 Correct 81 ms 155424 KB Output is correct
30 Correct 75 ms 153932 KB Output is correct
31 Correct 76 ms 154452 KB Output is correct
32 Correct 87 ms 154100 KB Output is correct
33 Correct 93 ms 157588 KB Output is correct
34 Correct 93 ms 157648 KB Output is correct
35 Correct 100 ms 158024 KB Output is correct
36 Correct 76 ms 154108 KB Output is correct
37 Correct 114 ms 160404 KB Output is correct
38 Correct 119 ms 160420 KB Output is correct
39 Correct 121 ms 160464 KB Output is correct
40 Correct 124 ms 160588 KB Output is correct
41 Correct 140 ms 160488 KB Output is correct
42 Correct 74 ms 153856 KB Output is correct
43 Correct 77 ms 153800 KB Output is correct
44 Correct 87 ms 153884 KB Output is correct
45 Correct 191 ms 171476 KB Output is correct
46 Correct 190 ms 171292 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 153180 KB Output is correct
2 Correct 70 ms 153212 KB Output is correct
3 Correct 72 ms 153196 KB Output is correct
4 Correct 74 ms 153128 KB Output is correct
5 Correct 70 ms 153116 KB Output is correct
6 Correct 71 ms 153112 KB Output is correct
7 Correct 71 ms 153160 KB Output is correct
8 Correct 71 ms 153208 KB Output is correct
9 Correct 76 ms 153200 KB Output is correct
10 Correct 78 ms 153668 KB Output is correct
11 Correct 72 ms 153356 KB Output is correct
12 Correct 72 ms 153240 KB Output is correct
13 Correct 71 ms 153188 KB Output is correct
14 Correct 73 ms 153548 KB Output is correct
15 Correct 72 ms 153516 KB Output is correct
16 Correct 72 ms 153424 KB Output is correct
17 Correct 75 ms 153832 KB Output is correct
18 Correct 72 ms 153552 KB Output is correct
19 Correct 72 ms 153380 KB Output is correct
20 Correct 73 ms 153328 KB Output is correct
21 Correct 72 ms 153440 KB Output is correct
22 Correct 72 ms 153480 KB Output is correct
23 Correct 72 ms 153512 KB Output is correct
24 Correct 73 ms 153808 KB Output is correct
25 Correct 75 ms 153568 KB Output is correct
26 Correct 72 ms 153580 KB Output is correct
27 Correct 73 ms 153428 KB Output is correct
28 Correct 80 ms 154280 KB Output is correct
29 Correct 82 ms 155488 KB Output is correct
30 Correct 75 ms 153924 KB Output is correct
31 Correct 77 ms 154444 KB Output is correct
32 Correct 76 ms 154180 KB Output is correct
33 Correct 94 ms 157676 KB Output is correct
34 Correct 96 ms 157652 KB Output is correct
35 Correct 110 ms 157932 KB Output is correct
36 Correct 86 ms 154060 KB Output is correct
37 Correct 126 ms 160332 KB Output is correct
38 Correct 129 ms 160352 KB Output is correct
39 Correct 122 ms 160356 KB Output is correct
40 Correct 118 ms 160256 KB Output is correct
41 Correct 119 ms 160296 KB Output is correct
42 Correct 76 ms 153768 KB Output is correct
43 Correct 75 ms 153672 KB Output is correct
44 Correct 76 ms 153752 KB Output is correct
45 Correct 191 ms 171332 KB Output is correct
46 Correct 187 ms 171320 KB Output is correct
47 Correct 323 ms 181636 KB Output is correct
48 Correct 110 ms 163212 KB Output is correct
49 Correct 104 ms 159780 KB Output is correct
50 Correct 105 ms 159712 KB Output is correct
51 Correct 178 ms 166908 KB Output is correct
52 Correct 175 ms 167912 KB Output is correct
53 Correct 108 ms 158528 KB Output is correct
54 Correct 74 ms 155044 KB Output is correct
55 Correct 77 ms 155888 KB Output is correct
56 Correct 91 ms 156224 KB Output is correct
57 Correct 190 ms 169560 KB Output is correct
58 Correct 84 ms 156520 KB Output is correct
59 Correct 91 ms 157532 KB Output is correct
60 Correct 97 ms 158440 KB Output is correct
61 Correct 100 ms 158096 KB Output is correct
62 Correct 202 ms 173692 KB Output is correct
63 Correct 965 ms 241244 KB Output is correct
64 Execution timed out 1096 ms 258308 KB Time limit exceeded
65 Halted 0 ms 0 KB -