oj.uz

Submission #400776

# Submission time Handle Problem Language Result Execution time Memory
400776 2021-05-08T16:08:22 Z BERNARB01 Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 339 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<vector<pair<int, long long>>> g(n);
	int target, start;
	for (int i = 0; i < m; i++) {
		int b, p;
		cin >> b >> p;
		if (i == 0) { 
			start = b;
		}
		if (i == 1) {
			target = b;
		}
		for (int j = 0; j < n; j++) {
			int d = abs(b - j);
			if (d % p == 0) {
				g[b].emplace_back(j, d / p);
			}
		}
	}
	const long long inf = (long long) 8e18L;
	vector<long long> dist(n, inf);
	priority_queue<pair<long long, int>> s;
	dist[start] = 0;
	s.emplace(0, start);
	while (!s.empty()) {
		long long exp = -s.top().first;
		int u = s.top().second;
		s.pop();
		if (exp != dist[u]) {
			continue;
		}
		for (auto [v, w] : g[u]) {
			if (dist[u] + w < dist[v]) {
				dist[v] = dist[u] + w;
				s.emplace(-dist[v], v);
			}
		}
	}
	cout << (dist[target] >= inf ? -1 : dist[target]) << '\n';
	return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:31:12: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |  dist[start] = 0;
      |            ^
skyscraper.cpp:47:22: warning: 'target' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |  cout << (dist[target] >= inf ? -1 : dist[target]) << '\n';
      |                      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 576 KB Output is correct
12 Correct 6 ms 4548 KB Output is correct
13 Correct 6 ms 4556 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 6 ms 4580 KB Output is correct
13 Correct 6 ms 4556 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 9 ms 824 KB Output is correct
18 Correct 11 ms 448 KB Output is correct
19 Correct 7 ms 460 KB Output is correct
20 Correct 75 ms 64560 KB Output is correct
21 Correct 4 ms 332 KB Output is correct
22 Correct 8 ms 444 KB Output is correct
23 Correct 10 ms 516 KB Output is correct
24 Correct 21 ms 628 KB Output is correct
25 Correct 24 ms 636 KB Output is correct
26 Correct 92 ms 66404 KB Output is correct
27 Correct 90 ms 66252 KB Output is correct
28 Correct 24 ms 836 KB Output is correct
29 Correct 13 ms 1868 KB Output is correct
30 Correct 4 ms 972 KB Output is correct
31 Correct 9 ms 1228 KB Output is correct
32 Correct 8 ms 972 KB Output is correct
33 Correct 29 ms 3104 KB Output is correct
34 Correct 29 ms 3120 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 576 KB Output is correct
12 Correct 6 ms 4548 KB Output is correct
13 Correct 6 ms 4556 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 3 ms 512 KB Output is correct
16 Correct 2 ms 464 KB Output is correct
17 Correct 9 ms 916 KB Output is correct
18 Correct 11 ms 460 KB Output is correct
19 Correct 7 ms 460 KB Output is correct
20 Correct 73 ms 64556 KB Output is correct
21 Correct 4 ms 332 KB Output is correct
22 Correct 8 ms 460 KB Output is correct
23 Correct 10 ms 540 KB Output is correct
24 Correct 21 ms 716 KB Output is correct
25 Correct 23 ms 660 KB Output is correct
26 Correct 92 ms 66284 KB Output is correct
27 Correct 90 ms 66176 KB Output is correct
28 Correct 24 ms 788 KB Output is correct
29 Correct 12 ms 1848 KB Output is correct
30 Correct 4 ms 972 KB Output is correct
31 Correct 9 ms 1232 KB Output is correct
32 Correct 8 ms 972 KB Output is correct
33 Correct 29 ms 3068 KB Output is correct
34 Correct 29 ms 3096 KB Output is correct
35 Correct 207 ms 4036 KB Output is correct
36 Correct 31 ms 824 KB Output is correct
37 Correct 214 ms 7348 KB Output is correct
38 Correct 332 ms 6148 KB Output is correct
39 Correct 335 ms 6548 KB Output is correct
40 Correct 339 ms 6244 KB Output is correct
41 Correct 334 ms 6152 KB Output is correct
42 Runtime error 254 ms 262148 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 244 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 6 ms 4548 KB Output is correct
13 Correct 6 ms 4556 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 10 ms 844 KB Output is correct
18 Correct 11 ms 460 KB Output is correct
19 Correct 7 ms 460 KB Output is correct
20 Correct 71 ms 64580 KB Output is correct
21 Correct 4 ms 332 KB Output is correct
22 Correct 8 ms 460 KB Output is correct
23 Correct 10 ms 484 KB Output is correct
24 Correct 21 ms 664 KB Output is correct
25 Correct 23 ms 628 KB Output is correct
26 Correct 93 ms 66324 KB Output is correct
27 Correct 92 ms 66148 KB Output is correct
28 Correct 24 ms 860 KB Output is correct
29 Correct 12 ms 1892 KB Output is correct
30 Correct 4 ms 972 KB Output is correct
31 Correct 10 ms 1228 KB Output is correct
32 Correct 9 ms 948 KB Output is correct
33 Correct 29 ms 3104 KB Output is correct
34 Correct 30 ms 3208 KB Output is correct
35 Correct 208 ms 4084 KB Output is correct
36 Correct 32 ms 816 KB Output is correct
37 Correct 215 ms 7284 KB Output is correct
38 Correct 337 ms 6400 KB Output is correct
39 Correct 333 ms 6596 KB Output is correct
40 Correct 334 ms 6340 KB Output is correct
41 Correct 337 ms 6140 KB Output is correct
42 Runtime error 245 ms 262148 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -