oj.uz

Submission #585361

# Submission time Handle Problem Language Result Execution time Memory
585361 2022-06-28T17:49:19 Z GusterGoose27 Jakarta Skyscrapers (APIO15_skyscraper) C++11
57 / 100
 1000 ms 31200 KB 
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int, int> pii;
 
const int MAXN = 3e4;
const int inf = 1e9;
vector<pii> edges[MAXN];
unordered_set<int> at[MAXN];
int n, m;
int dist[MAXN];
vector<int> jump_occs[MAXN+1];
int occ_pos[MAXN+1];
vector<int> valsat[MAXN];
 
void dijkstra(int s) {
	fill(dist, dist+n, inf);
	dist[s] = 0;
	priority_queue<pii> pq;
	pq.push(pii(0, s));
	while (!pq.empty()) {
		pii p = pq.top();
		pq.pop();
		int cur = p.second;
		if (dist[cur] < p.first) continue;
		for (pii e: edges[cur]) {
			if (dist[cur]+e.second < dist[e.first]) {
				dist[e.first] = dist[cur]+e.second;
				pq.push(pii(dist[e.first], e.first));
			}
		}
	}
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	int posf;
	int poss;
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y;
		if (i == 1) posf = x;
		if (i == 0) poss = x;
		jump_occs[y].push_back(x);
		occ_pos[y]++;
		//valsat[x].push_back(y);
		at[x].insert(y);
	}
	for (int i = n-1; i >= 0; i--) {
		for (int p: at[i]) {
			occ_pos[p]--;
			int cur = occ_pos[p];
			int psize = jump_occs[p].size();
			for (int j = i+p; j < n; j += p) {
				edges[i].push_back(pii(j, (j-i)/p));
				while (cur < psize && jump_occs[p][cur] < j) cur++;
				if (cur < psize && jump_occs[p][cur] == j) break;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int p: at[i]) {
			int cur = occ_pos[p];
			for (int j = i-p; j >= 0; j -= p) {
				edges[i].push_back(pii(j, (i-j)/p));
				while (cur >= 0 && jump_occs[p][cur] > j) cur--;
				if (cur >= 0 && jump_occs[p][cur] == j) break;
			}
			occ_pos[p]++;
		}
	}
	dijkstra(poss);
	cout << ((dist[posf] == inf) ? (-1) : dist[posf]) << "\n";
	return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:75:10: warning: 'poss' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |  dijkstra(poss);
      |  ~~~~~~~~^~~~~~
skyscraper.cpp:76:21: warning: 'posf' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |  cout << ((dist[posf] == inf) ? (-1) : dist[posf]) << "\n";
      |            ~~~~~~~~~^

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4052 KB Output is correct
2 Correct 3 ms 4052 KB Output is correct
3 Correct 3 ms 4052 KB Output is correct
4 Correct 2 ms 4052 KB Output is correct
5 Correct 3 ms 4052 KB Output is correct
6 Correct 2 ms 4052 KB Output is correct
7 Correct 2 ms 4052 KB Output is correct
8 Correct 4 ms 4052 KB Output is correct
9 Correct 11 ms 4040 KB Output is correct
10 Correct 3 ms 4052 KB Output is correct
11 Correct 3 ms 4180 KB Output is correct
12 Correct 3 ms 4052 KB Output is correct
13 Correct 3 ms 4180 KB Output is correct
14 Correct 3 ms 4180 KB Output is correct
15 Correct 3 ms 4180 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4052 KB Output is correct
2 Correct 2 ms 4052 KB Output is correct
3 Correct 3 ms 4052 KB Output is correct
4 Correct 4 ms 4052 KB Output is correct
5 Correct 3 ms 4052 KB Output is correct
6 Correct 2 ms 4052 KB Output is correct
7 Correct 2 ms 4052 KB Output is correct
8 Correct 3 ms 4052 KB Output is correct
9 Correct 3 ms 4052 KB Output is correct
10 Correct 4 ms 4052 KB Output is correct
11 Correct 4 ms 4180 KB Output is correct
12 Correct 3 ms 4052 KB Output is correct
13 Correct 3 ms 4152 KB Output is correct
14 Correct 3 ms 4272 KB Output is correct
15 Correct 3 ms 4180 KB Output is correct
16 Correct 4 ms 4180 KB Output is correct
17 Correct 17 ms 4456 KB Output is correct
18 Correct 3 ms 4308 KB Output is correct
19 Correct 3 ms 4180 KB Output is correct
20 Correct 36 ms 26060 KB Output is correct
21 Correct 3 ms 4180 KB Output is correct
22 Correct 3 ms 4172 KB Output is correct
23 Correct 6 ms 4308 KB Output is correct
24 Correct 28 ms 4492 KB Output is correct
25 Correct 6 ms 4456 KB Output is correct
26 Correct 3 ms 4180 KB Output is correct
27 Correct 5 ms 4180 KB Output is correct
28 Correct 4 ms 4564 KB Output is correct
29 Correct 5 ms 4820 KB Output is correct
30 Correct 5 ms 4308 KB Output is correct
31 Correct 7 ms 4436 KB Output is correct
32 Correct 4 ms 4308 KB Output is correct
33 Correct 6 ms 5332 KB Output is correct
34 Correct 7 ms 5332 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4052 KB Output is correct
2 Correct 2 ms 4052 KB Output is correct
3 Correct 2 ms 4052 KB Output is correct
4 Correct 2 ms 4052 KB Output is correct
5 Correct 2 ms 4052 KB Output is correct
6 Correct 3 ms 3972 KB Output is correct
7 Correct 2 ms 4052 KB Output is correct
8 Correct 3 ms 4052 KB Output is correct
9 Correct 3 ms 4052 KB Output is correct
10 Correct 3 ms 4052 KB Output is correct
11 Correct 5 ms 4180 KB Output is correct
12 Correct 3 ms 4052 KB Output is correct
13 Correct 3 ms 4180 KB Output is correct
14 Correct 3 ms 4180 KB Output is correct
15 Correct 3 ms 4180 KB Output is correct
16 Correct 3 ms 4180 KB Output is correct
17 Correct 18 ms 4436 KB Output is correct
18 Correct 3 ms 4316 KB Output is correct
19 Correct 3 ms 4180 KB Output is correct
20 Correct 35 ms 26044 KB Output is correct
21 Correct 3 ms 4180 KB Output is correct
22 Correct 3 ms 4180 KB Output is correct
23 Correct 6 ms 4308 KB Output is correct
24 Correct 32 ms 4436 KB Output is correct
25 Correct 7 ms 4436 KB Output is correct
26 Correct 3 ms 4180 KB Output is correct
27 Correct 4 ms 4180 KB Output is correct
28 Correct 4 ms 4636 KB Output is correct
29 Correct 5 ms 4820 KB Output is correct
30 Correct 4 ms 4308 KB Output is correct
31 Correct 6 ms 4528 KB Output is correct
32 Correct 4 ms 4308 KB Output is correct
33 Correct 6 ms 5332 KB Output is correct
34 Correct 5 ms 5332 KB Output is correct
35 Correct 123 ms 6692 KB Output is correct
36 Correct 25 ms 4608 KB Output is correct
37 Correct 302 ms 7832 KB Output is correct
38 Correct 280 ms 7852 KB Output is correct
39 Correct 341 ms 8012 KB Output is correct
40 Correct 356 ms 7904 KB Output is correct
41 Correct 321 ms 7708 KB Output is correct
42 Correct 6 ms 4308 KB Output is correct
43 Correct 6 ms 4308 KB Output is correct
44 Correct 45 ms 31200 KB Output is correct
45 Correct 19 ms 9856 KB Output is correct
46 Correct 19 ms 9868 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4052 KB Output is correct
2 Correct 2 ms 4052 KB Output is correct
3 Correct 2 ms 4052 KB Output is correct
4 Correct 2 ms 4052 KB Output is correct
5 Correct 3 ms 4088 KB Output is correct
6 Correct 4 ms 4052 KB Output is correct
7 Correct 3 ms 4052 KB Output is correct
8 Correct 3 ms 4032 KB Output is correct
9 Correct 3 ms 4052 KB Output is correct
10 Correct 3 ms 4052 KB Output is correct
11 Correct 4 ms 4180 KB Output is correct
12 Correct 3 ms 4052 KB Output is correct
13 Correct 3 ms 4180 KB Output is correct
14 Correct 3 ms 4180 KB Output is correct
15 Correct 3 ms 4180 KB Output is correct
16 Correct 3 ms 4180 KB Output is correct
17 Correct 18 ms 4436 KB Output is correct
18 Correct 3 ms 4308 KB Output is correct
19 Correct 3 ms 4180 KB Output is correct
20 Correct 35 ms 26000 KB Output is correct
21 Correct 3 ms 4180 KB Output is correct
22 Correct 3 ms 4180 KB Output is correct
23 Correct 7 ms 4308 KB Output is correct
24 Correct 28 ms 4436 KB Output is correct
25 Correct 6 ms 4452 KB Output is correct
26 Correct 3 ms 4180 KB Output is correct
27 Correct 3 ms 4180 KB Output is correct
28 Correct 4 ms 4564 KB Output is correct
29 Correct 4 ms 4820 KB Output is correct
30 Correct 4 ms 4308 KB Output is correct
31 Correct 5 ms 4436 KB Output is correct
32 Correct 4 ms 4308 KB Output is correct
33 Correct 6 ms 5332 KB Output is correct
34 Correct 5 ms 5332 KB Output is correct
35 Correct 140 ms 6716 KB Output is correct
36 Correct 26 ms 4564 KB Output is correct
37 Correct 291 ms 7832 KB Output is correct
38 Correct 313 ms 7884 KB Output is correct
39 Correct 315 ms 7952 KB Output is correct
40 Correct 341 ms 7904 KB Output is correct
41 Correct 352 ms 7800 KB Output is correct
42 Correct 6 ms 4308 KB Output is correct
43 Correct 6 ms 4372 KB Output is correct
44 Correct 49 ms 31144 KB Output is correct
45 Correct 22 ms 10000 KB Output is correct
46 Correct 21 ms 9784 KB Output is correct
47 Execution timed out 1084 ms 16152 KB Time limit exceeded
48 Halted 0 ms 0 KB -