oj.uz

Submission #771259

# Submission time Handle Problem Language Result Execution time Memory
771259 2023-07-02T18:20:22 Z IBory Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 1000 ms 241188 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];
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 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();

		vector<int> next2;
		if (N < cur) {
			if (!noL[cur]) next2.push_back(cur - 1);
			if (!noR[cur]) next2.push_back(cur + 1);
		}
		for (int n : next2) G[cur].push_back(n);

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

		for (int i = 0; i < next2.size(); ++i) G[cur].pop_back();
	}

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

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:26:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |  for (auto& [q, v] : make) {
      |             ^
skyscraper.cpp:27:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |   auto [p, i] = q;
      |        ^
skyscraper.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for (int i = 0; i < next2.size(); ++i) G[cur].pop_back();
      |                   ~~^~~~~~~~~~~~~~
skyscraper.cpp:83:15: warning: 'EN' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |  cout << (D[EN] > 1E9 ? -1 : D[EN]);
      |           ~~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 153184 KB Output is correct
2 Correct 62 ms 153144 KB Output is correct
3 Correct 61 ms 153160 KB Output is correct
4 Correct 61 ms 153116 KB Output is correct
5 Correct 62 ms 153204 KB Output is correct
6 Correct 61 ms 153176 KB Output is correct
7 Correct 60 ms 153108 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 153124 KB Output is correct
2 Correct 61 ms 153120 KB Output is correct
3 Correct 61 ms 153224 KB Output is correct
4 Correct 60 ms 153108 KB Output is correct
5 Correct 61 ms 153128 KB Output is correct
6 Correct 61 ms 153224 KB Output is correct
7 Correct 62 ms 153192 KB Output is correct
8 Correct 59 ms 153172 KB Output is correct
9 Correct 61 ms 153156 KB Output is correct
10 Correct 61 ms 153288 KB Output is correct
11 Correct 62 ms 153420 KB Output is correct
12 Correct 62 ms 153260 KB Output is correct
13 Correct 61 ms 153200 KB Output is correct
14 Correct 63 ms 153596 KB Output is correct
15 Correct 62 ms 153540 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 153140 KB Output is correct
2 Correct 60 ms 153148 KB Output is correct
3 Correct 61 ms 153120 KB Output is correct
4 Correct 61 ms 153224 KB Output is correct
5 Correct 61 ms 153192 KB Output is correct
6 Correct 62 ms 153180 KB Output is correct
7 Correct 61 ms 153136 KB Output is correct
8 Correct 61 ms 153232 KB Output is correct
9 Correct 61 ms 153184 KB Output is correct
10 Correct 61 ms 153272 KB Output is correct
11 Correct 62 ms 153456 KB Output is correct
12 Correct 68 ms 153420 KB Output is correct
13 Correct 62 ms 153136 KB Output is correct
14 Correct 64 ms 153468 KB Output is correct
15 Correct 63 ms 153480 KB Output is correct
16 Correct 61 ms 153400 KB Output is correct
17 Correct 66 ms 153776 KB Output is correct
18 Correct 69 ms 153540 KB Output is correct
19 Correct 63 ms 153420 KB Output is correct
20 Correct 61 ms 153296 KB Output is correct
21 Correct 62 ms 153388 KB Output is correct
22 Correct 61 ms 153408 KB Output is correct
23 Correct 62 ms 153492 KB Output is correct
24 Correct 64 ms 153776 KB Output is correct
25 Correct 64 ms 153636 KB Output is correct
26 Correct 63 ms 153548 KB Output is correct
27 Correct 63 ms 153528 KB Output is correct
28 Correct 66 ms 154224 KB Output is correct
29 Correct 75 ms 155496 KB Output is correct
30 Correct 66 ms 153880 KB Output is correct
31 Correct 69 ms 154552 KB Output is correct
32 Correct 66 ms 154176 KB Output is correct
33 Correct 88 ms 157636 KB Output is correct
34 Correct 91 ms 157772 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 153148 KB Output is correct
2 Correct 59 ms 153228 KB Output is correct
3 Correct 68 ms 153164 KB Output is correct
4 Correct 58 ms 153164 KB Output is correct
5 Correct 60 ms 153224 KB Output is correct
6 Correct 61 ms 153136 KB Output is correct
7 Correct 60 ms 153160 KB Output is correct
8 Correct 61 ms 153168 KB Output is correct
9 Correct 61 ms 153132 KB Output is correct
10 Correct 64 ms 153284 KB Output is correct
11 Correct 63 ms 153404 KB Output is correct
12 Correct 60 ms 153184 KB Output is correct
13 Correct 60 ms 153136 KB Output is correct
14 Correct 62 ms 153596 KB Output is correct
15 Correct 61 ms 153564 KB Output is correct
16 Correct 58 ms 153420 KB Output is correct
17 Correct 70 ms 153876 KB Output is correct
18 Correct 66 ms 153548 KB Output is correct
19 Correct 62 ms 153420 KB Output is correct
20 Correct 61 ms 153364 KB Output is correct
21 Correct 70 ms 153552 KB Output is correct
22 Correct 61 ms 153448 KB Output is correct
23 Correct 61 ms 153492 KB Output is correct
24 Correct 63 ms 153740 KB Output is correct
25 Correct 61 ms 153548 KB Output is correct
26 Correct 61 ms 153560 KB Output is correct
27 Correct 61 ms 153516 KB Output is correct
28 Correct 66 ms 154256 KB Output is correct
29 Correct 73 ms 155428 KB Output is correct
30 Correct 65 ms 153896 KB Output is correct
31 Correct 67 ms 154536 KB Output is correct
32 Correct 64 ms 154108 KB Output is correct
33 Correct 89 ms 157600 KB Output is correct
34 Correct 88 ms 157656 KB Output is correct
35 Correct 93 ms 157728 KB Output is correct
36 Correct 70 ms 154008 KB Output is correct
37 Correct 107 ms 160204 KB Output is correct
38 Correct 113 ms 160128 KB Output is correct
39 Correct 111 ms 160200 KB Output is correct
40 Correct 111 ms 160200 KB Output is correct
41 Correct 113 ms 160172 KB Output is correct
42 Correct 63 ms 153616 KB Output is correct
43 Correct 63 ms 153620 KB Output is correct
44 Correct 62 ms 153612 KB Output is correct
45 Correct 204 ms 171208 KB Output is correct
46 Correct 239 ms 171440 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 153168 KB Output is correct
2 Correct 64 ms 153180 KB Output is correct
3 Correct 65 ms 153128 KB Output is correct
4 Correct 66 ms 153164 KB Output is correct
5 Correct 69 ms 153252 KB Output is correct
6 Correct 63 ms 153100 KB Output is correct
7 Correct 64 ms 153116 KB Output is correct
8 Correct 64 ms 153164 KB Output is correct
9 Correct 75 ms 153164 KB Output is correct
10 Correct 76 ms 153220 KB Output is correct
11 Correct 67 ms 153420 KB Output is correct
12 Correct 68 ms 153256 KB Output is correct
13 Correct 67 ms 153252 KB Output is correct
14 Correct 68 ms 153556 KB Output is correct
15 Correct 68 ms 153548 KB Output is correct
16 Correct 67 ms 153332 KB Output is correct
17 Correct 73 ms 153804 KB Output is correct
18 Correct 66 ms 153544 KB Output is correct
19 Correct 66 ms 153376 KB Output is correct
20 Correct 66 ms 153404 KB Output is correct
21 Correct 68 ms 153364 KB Output is correct
22 Correct 68 ms 153420 KB Output is correct
23 Correct 69 ms 153556 KB Output is correct
24 Correct 70 ms 153824 KB Output is correct
25 Correct 69 ms 153616 KB Output is correct
26 Correct 69 ms 153456 KB Output is correct
27 Correct 68 ms 153524 KB Output is correct
28 Correct 72 ms 154228 KB Output is correct
29 Correct 83 ms 155432 KB Output is correct
30 Correct 71 ms 153908 KB Output is correct
31 Correct 76 ms 154564 KB Output is correct
32 Correct 73 ms 154136 KB Output is correct
33 Correct 94 ms 157668 KB Output is correct
34 Correct 101 ms 157976 KB Output is correct
35 Correct 101 ms 157948 KB Output is correct
36 Correct 72 ms 154108 KB Output is correct
37 Correct 116 ms 160216 KB Output is correct
38 Correct 122 ms 160368 KB Output is correct
39 Correct 119 ms 160320 KB Output is correct
40 Correct 117 ms 160244 KB Output is correct
41 Correct 117 ms 160276 KB Output is correct
42 Correct 69 ms 153656 KB Output is correct
43 Correct 70 ms 153632 KB Output is correct
44 Correct 71 ms 153844 KB Output is correct
45 Correct 205 ms 171308 KB Output is correct
46 Correct 205 ms 171264 KB Output is correct
47 Correct 334 ms 181684 KB Output is correct
48 Correct 108 ms 163208 KB Output is correct
49 Correct 95 ms 159768 KB Output is correct
50 Correct 92 ms 159524 KB Output is correct
51 Correct 179 ms 166800 KB Output is correct
52 Correct 194 ms 168000 KB Output is correct
53 Correct 108 ms 158320 KB Output is correct
54 Correct 69 ms 154984 KB Output is correct
55 Correct 72 ms 155848 KB Output is correct
56 Correct 78 ms 156152 KB Output is correct
57 Correct 174 ms 169644 KB Output is correct
58 Correct 81 ms 156424 KB Output is correct
59 Correct 91 ms 157496 KB Output is correct
60 Correct 98 ms 158496 KB Output is correct
61 Correct 96 ms 158148 KB Output is correct
62 Correct 217 ms 173724 KB Output is correct
63 Execution timed out 1088 ms 241188 KB Time limit exceeded
64 Halted 0 ms 0 KB -