oj.uz

Submission #826698

# Submission time Handle Problem Language Result Execution time Memory
826698 2023-08-15T21:08:56 Z happypotato Jakarta Skyscrapers (APIO15_skyscraper) C++17
100 / 100
 559 ms 225668 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
const int MAX = 1e9;
const int mxN = 3e4;
const int SQRT = 80;
pii doge[mxN];
vector<pii> adj[mxN * (SQRT + 1)];
int dist[mxN * (SQRT + 1)];
void AddEdge(int u, int v, int w) {
	adj[u].pb({v, w});
}
int n;
void init() {
	for (int i = 0; i < mxN * (SQRT + 1); i++) {
		adj[i].clear();
		dist[i] = MAX;
	}
	// dummy nodes for P_i < SQRT
	for (int diff = 1; diff <= min(n, SQRT); diff++) {
		for (int i = 0; i < n; i++) {
			AddEdge(diff * mxN + i, i, 0);
		}
		for (int i = diff; i < n; i++) {
			int u = diff * mxN + (i - diff);
			int v = diff * mxN + i;
			AddEdge(u, v, 1);
			AddEdge(v, u, 1);
		}
	}
}
void solve() {
	int m;
	cin >> n >> m;
	init();
	for (int i = 0; i < m; i++) {
		cin >> doge[i].ff >> doge[i].ss;
		if (doge[i].ss <= SQRT) {
			// connect to dummy nodes
			AddEdge(doge[i].ff, doge[i].ss * mxN + doge[i].ff, 0);
		} else {
			// connect actual edges
			for (int step = 1; doge[i].ff + doge[i].ss * step < n; step++) {
				AddEdge(doge[i].ff, doge[i].ff + doge[i].ss * step, step);
			}
			for (int step = 1; doge[i].ff - doge[i].ss * step >= 0; step++) {
				AddEdge(doge[i].ff, doge[i].ff - doge[i].ss * step, step);
			}
		}
	}
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0, doge[0].ff});
	dist[doge[0].ff] = 0;
	while (!pq.empty()) {
		pii cur = pq.top();
		pq.pop();
		if (dist[cur.ss] > cur.ff) continue;
		for (pii &v : adj[cur.ss]) {
			if (cur.ff + v.ss >= dist[v.ff]) continue;
			dist[v.ff] = cur.ff + v.ss;
			pq.push({dist[v.ff], v.ff});
		}
	}
	int ans = dist[doge[1].ff];
	cout << (ans >= MAX ? -1 : ans) << endl;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 66844 KB Output is correct
2 Correct 39 ms 66844 KB Output is correct
3 Correct 38 ms 66832 KB Output is correct
4 Correct 37 ms 66844 KB Output is correct
5 Correct 38 ms 66764 KB Output is correct
6 Correct 37 ms 66820 KB Output is correct
7 Correct 37 ms 66844 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 66884 KB Output is correct
2 Correct 40 ms 66840 KB Output is correct
3 Correct 38 ms 66772 KB Output is correct
4 Correct 38 ms 66756 KB Output is correct
5 Correct 38 ms 66768 KB Output is correct
6 Correct 38 ms 66900 KB Output is correct
7 Correct 37 ms 66860 KB Output is correct
8 Correct 38 ms 66804 KB Output is correct
9 Correct 37 ms 66920 KB Output is correct
10 Correct 39 ms 67092 KB Output is correct
11 Correct 38 ms 67212 KB Output is correct
12 Correct 38 ms 67240 KB Output is correct
13 Correct 38 ms 67200 KB Output is correct
14 Correct 44 ms 67224 KB Output is correct
15 Correct 40 ms 67152 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 66820 KB Output is correct
2 Correct 37 ms 66856 KB Output is correct
3 Correct 38 ms 66764 KB Output is correct
4 Correct 38 ms 66820 KB Output is correct
5 Correct 39 ms 66868 KB Output is correct
6 Correct 37 ms 66828 KB Output is correct
7 Correct 37 ms 66768 KB Output is correct
8 Correct 37 ms 66872 KB Output is correct
9 Correct 38 ms 66900 KB Output is correct
10 Correct 38 ms 67136 KB Output is correct
11 Correct 40 ms 67244 KB Output is correct
12 Correct 38 ms 67148 KB Output is correct
13 Correct 38 ms 67112 KB Output is correct
14 Correct 38 ms 67188 KB Output is correct
15 Correct 38 ms 67148 KB Output is correct
16 Correct 39 ms 67516 KB Output is correct
17 Correct 45 ms 69604 KB Output is correct
18 Correct 51 ms 73308 KB Output is correct
19 Correct 54 ms 74340 KB Output is correct
20 Correct 54 ms 74364 KB Output is correct
21 Correct 40 ms 68176 KB Output is correct
22 Correct 50 ms 73516 KB Output is correct
23 Correct 49 ms 72836 KB Output is correct
24 Correct 54 ms 73912 KB Output is correct
25 Correct 54 ms 74316 KB Output is correct
26 Correct 54 ms 74296 KB Output is correct
27 Correct 54 ms 74284 KB Output is correct
28 Correct 55 ms 74268 KB Output is correct
29 Correct 57 ms 74252 KB Output is correct
30 Correct 54 ms 74356 KB Output is correct
31 Correct 55 ms 74316 KB Output is correct
32 Correct 60 ms 74324 KB Output is correct
33 Correct 61 ms 74396 KB Output is correct
34 Correct 61 ms 74332 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 66832 KB Output is correct
2 Correct 38 ms 66888 KB Output is correct
3 Correct 39 ms 66872 KB Output is correct
4 Correct 39 ms 66816 KB Output is correct
5 Correct 39 ms 66880 KB Output is correct
6 Correct 39 ms 66780 KB Output is correct
7 Correct 43 ms 66900 KB Output is correct
8 Correct 38 ms 66948 KB Output is correct
9 Correct 39 ms 66980 KB Output is correct
10 Correct 39 ms 67108 KB Output is correct
11 Correct 40 ms 67216 KB Output is correct
12 Correct 40 ms 67224 KB Output is correct
13 Correct 40 ms 67188 KB Output is correct
14 Correct 39 ms 67156 KB Output is correct
15 Correct 39 ms 67232 KB Output is correct
16 Correct 39 ms 67516 KB Output is correct
17 Correct 44 ms 69616 KB Output is correct
18 Correct 51 ms 73364 KB Output is correct
19 Correct 58 ms 74388 KB Output is correct
20 Correct 54 ms 74348 KB Output is correct
21 Correct 41 ms 68180 KB Output is correct
22 Correct 51 ms 73504 KB Output is correct
23 Correct 50 ms 72844 KB Output is correct
24 Correct 53 ms 74016 KB Output is correct
25 Correct 54 ms 74356 KB Output is correct
26 Correct 54 ms 74276 KB Output is correct
27 Correct 53 ms 74348 KB Output is correct
28 Correct 54 ms 74396 KB Output is correct
29 Correct 57 ms 74260 KB Output is correct
30 Correct 54 ms 74308 KB Output is correct
31 Correct 55 ms 74320 KB Output is correct
32 Correct 55 ms 74364 KB Output is correct
33 Correct 60 ms 74320 KB Output is correct
34 Correct 61 ms 74392 KB Output is correct
35 Correct 59 ms 72884 KB Output is correct
36 Correct 49 ms 70876 KB Output is correct
37 Correct 68 ms 75400 KB Output is correct
38 Correct 69 ms 75504 KB Output is correct
39 Correct 70 ms 75504 KB Output is correct
40 Correct 68 ms 75484 KB Output is correct
41 Correct 69 ms 75432 KB Output is correct
42 Correct 62 ms 74932 KB Output is correct
43 Correct 57 ms 74856 KB Output is correct
44 Correct 57 ms 74884 KB Output is correct
45 Correct 72 ms 78416 KB Output is correct
46 Correct 72 ms 78448 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 66836 KB Output is correct
2 Correct 38 ms 66900 KB Output is correct
3 Correct 41 ms 66764 KB Output is correct
4 Correct 39 ms 66772 KB Output is correct
5 Correct 38 ms 66792 KB Output is correct
6 Correct 37 ms 66892 KB Output is correct
7 Correct 39 ms 66816 KB Output is correct
8 Correct 38 ms 66896 KB Output is correct
9 Correct 38 ms 66928 KB Output is correct
10 Correct 39 ms 67156 KB Output is correct
11 Correct 39 ms 67144 KB Output is correct
12 Correct 40 ms 67096 KB Output is correct
13 Correct 38 ms 67168 KB Output is correct
14 Correct 38 ms 67220 KB Output is correct
15 Correct 40 ms 67136 KB Output is correct
16 Correct 39 ms 67476 KB Output is correct
17 Correct 44 ms 69648 KB Output is correct
18 Correct 52 ms 73328 KB Output is correct
19 Correct 53 ms 74276 KB Output is correct
20 Correct 52 ms 74344 KB Output is correct
21 Correct 42 ms 68176 KB Output is correct
22 Correct 51 ms 73472 KB Output is correct
23 Correct 51 ms 72800 KB Output is correct
24 Correct 56 ms 73936 KB Output is correct
25 Correct 53 ms 74316 KB Output is correct
26 Correct 62 ms 74320 KB Output is correct
27 Correct 53 ms 74316 KB Output is correct
28 Correct 54 ms 74396 KB Output is correct
29 Correct 59 ms 74316 KB Output is correct
30 Correct 54 ms 74316 KB Output is correct
31 Correct 55 ms 74256 KB Output is correct
32 Correct 55 ms 74276 KB Output is correct
33 Correct 60 ms 74316 KB Output is correct
34 Correct 59 ms 74340 KB Output is correct
35 Correct 58 ms 72812 KB Output is correct
36 Correct 47 ms 70932 KB Output is correct
37 Correct 68 ms 75312 KB Output is correct
38 Correct 69 ms 75472 KB Output is correct
39 Correct 69 ms 75472 KB Output is correct
40 Correct 70 ms 75440 KB Output is correct
41 Correct 68 ms 75468 KB Output is correct
42 Correct 57 ms 74856 KB Output is correct
43 Correct 61 ms 74828 KB Output is correct
44 Correct 58 ms 74840 KB Output is correct
45 Correct 71 ms 78412 KB Output is correct
46 Correct 72 ms 78348 KB Output is correct
47 Correct 258 ms 118404 KB Output is correct
48 Correct 226 ms 155440 KB Output is correct
49 Correct 262 ms 163440 KB Output is correct
50 Correct 265 ms 172692 KB Output is correct
51 Correct 317 ms 181928 KB Output is correct
52 Correct 320 ms 182032 KB Output is correct
53 Correct 284 ms 179856 KB Output is correct
54 Correct 274 ms 179416 KB Output is correct
55 Correct 279 ms 179452 KB Output is correct
56 Correct 279 ms 180692 KB Output is correct
57 Correct 355 ms 179632 KB Output is correct
58 Correct 288 ms 180136 KB Output is correct
59 Correct 288 ms 180092 KB Output is correct
60 Correct 316 ms 180660 KB Output is correct
61 Correct 303 ms 180308 KB Output is correct
62 Correct 299 ms 182512 KB Output is correct
63 Correct 340 ms 204228 KB Output is correct
64 Correct 349 ms 212324 KB Output is correct
65 Correct 373 ms 218448 KB Output is correct
66 Correct 558 ms 225496 KB Output is correct
67 Correct 559 ms 225668 KB Output is correct