oj.uz

Submission #826697

# Submission time Handle Problem Language Result Execution time Memory
826697 2023-08-15T21:07:29 Z happypotato Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 429 ms 262144 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 = 100;
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 45 ms 83276 KB Output is correct
2 Correct 45 ms 83284 KB Output is correct
3 Correct 44 ms 83284 KB Output is correct
4 Correct 46 ms 83228 KB Output is correct
5 Correct 47 ms 83272 KB Output is correct
6 Correct 46 ms 83276 KB Output is correct
7 Correct 47 ms 83232 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 83284 KB Output is correct
2 Correct 47 ms 83268 KB Output is correct
3 Correct 46 ms 83284 KB Output is correct
4 Correct 46 ms 83260 KB Output is correct
5 Correct 47 ms 83240 KB Output is correct
6 Correct 45 ms 83284 KB Output is correct
7 Correct 46 ms 83200 KB Output is correct
8 Correct 46 ms 83300 KB Output is correct
9 Correct 46 ms 83404 KB Output is correct
10 Correct 48 ms 83604 KB Output is correct
11 Correct 49 ms 83660 KB Output is correct
12 Correct 48 ms 83628 KB Output is correct
13 Correct 47 ms 83644 KB Output is correct
14 Correct 47 ms 83656 KB Output is correct
15 Correct 47 ms 83756 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 83316 KB Output is correct
2 Correct 46 ms 83260 KB Output is correct
3 Correct 46 ms 83228 KB Output is correct
4 Correct 47 ms 83300 KB Output is correct
5 Correct 48 ms 83212 KB Output is correct
6 Correct 46 ms 83220 KB Output is correct
7 Correct 47 ms 83276 KB Output is correct
8 Correct 47 ms 83280 KB Output is correct
9 Correct 45 ms 83400 KB Output is correct
10 Correct 47 ms 83588 KB Output is correct
11 Correct 48 ms 83724 KB Output is correct
12 Correct 47 ms 83704 KB Output is correct
13 Correct 50 ms 83776 KB Output is correct
14 Correct 47 ms 83752 KB Output is correct
15 Correct 48 ms 83660 KB Output is correct
16 Correct 48 ms 84124 KB Output is correct
17 Correct 55 ms 86732 KB Output is correct
18 Correct 63 ms 91340 KB Output is correct
19 Correct 65 ms 92576 KB Output is correct
20 Correct 66 ms 92584 KB Output is correct
21 Correct 52 ms 84992 KB Output is correct
22 Correct 99 ms 91588 KB Output is correct
23 Correct 61 ms 90696 KB Output is correct
24 Correct 71 ms 92128 KB Output is correct
25 Correct 66 ms 92520 KB Output is correct
26 Correct 69 ms 92624 KB Output is correct
27 Correct 67 ms 92568 KB Output is correct
28 Correct 66 ms 92652 KB Output is correct
29 Correct 69 ms 92536 KB Output is correct
30 Correct 66 ms 92492 KB Output is correct
31 Correct 67 ms 92496 KB Output is correct
32 Correct 67 ms 92620 KB Output is correct
33 Correct 72 ms 92652 KB Output is correct
34 Correct 72 ms 92620 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 83300 KB Output is correct
2 Correct 45 ms 83260 KB Output is correct
3 Correct 47 ms 83276 KB Output is correct
4 Correct 46 ms 83308 KB Output is correct
5 Correct 45 ms 83244 KB Output is correct
6 Correct 46 ms 83304 KB Output is correct
7 Correct 44 ms 83216 KB Output is correct
8 Correct 46 ms 83280 KB Output is correct
9 Correct 46 ms 83404 KB Output is correct
10 Correct 47 ms 83688 KB Output is correct
11 Correct 47 ms 83704 KB Output is correct
12 Correct 46 ms 83668 KB Output is correct
13 Correct 47 ms 83660 KB Output is correct
14 Correct 47 ms 83628 KB Output is correct
15 Correct 48 ms 83660 KB Output is correct
16 Correct 48 ms 84116 KB Output is correct
17 Correct 54 ms 86728 KB Output is correct
18 Correct 63 ms 91340 KB Output is correct
19 Correct 65 ms 92576 KB Output is correct
20 Correct 67 ms 92584 KB Output is correct
21 Correct 50 ms 85004 KB Output is correct
22 Correct 63 ms 91504 KB Output is correct
23 Correct 65 ms 90652 KB Output is correct
24 Correct 66 ms 92152 KB Output is correct
25 Correct 67 ms 92628 KB Output is correct
26 Correct 69 ms 92524 KB Output is correct
27 Correct 79 ms 92640 KB Output is correct
28 Correct 67 ms 92576 KB Output is correct
29 Correct 77 ms 92684 KB Output is correct
30 Correct 69 ms 92608 KB Output is correct
31 Correct 68 ms 92588 KB Output is correct
32 Correct 70 ms 92492 KB Output is correct
33 Correct 73 ms 92648 KB Output is correct
34 Correct 75 ms 92620 KB Output is correct
35 Correct 84 ms 90572 KB Output is correct
36 Correct 59 ms 88324 KB Output is correct
37 Correct 86 ms 93392 KB Output is correct
38 Correct 83 ms 93628 KB Output is correct
39 Correct 84 ms 93644 KB Output is correct
40 Correct 87 ms 93620 KB Output is correct
41 Correct 83 ms 93600 KB Output is correct
42 Correct 69 ms 93192 KB Output is correct
43 Correct 68 ms 93204 KB Output is correct
44 Correct 70 ms 93104 KB Output is correct
45 Correct 87 ms 95948 KB Output is correct
46 Correct 88 ms 95960 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 83296 KB Output is correct
2 Correct 47 ms 83236 KB Output is correct
3 Correct 47 ms 83280 KB Output is correct
4 Correct 46 ms 83320 KB Output is correct
5 Correct 46 ms 83292 KB Output is correct
6 Correct 46 ms 83272 KB Output is correct
7 Correct 47 ms 83268 KB Output is correct
8 Correct 47 ms 83368 KB Output is correct
9 Correct 47 ms 83432 KB Output is correct
10 Correct 55 ms 83616 KB Output is correct
11 Correct 52 ms 83692 KB Output is correct
12 Correct 47 ms 83608 KB Output is correct
13 Correct 47 ms 83624 KB Output is correct
14 Correct 46 ms 83656 KB Output is correct
15 Correct 47 ms 83664 KB Output is correct
16 Correct 49 ms 84044 KB Output is correct
17 Correct 57 ms 86640 KB Output is correct
18 Correct 68 ms 91392 KB Output is correct
19 Correct 65 ms 92576 KB Output is correct
20 Correct 67 ms 92644 KB Output is correct
21 Correct 50 ms 85008 KB Output is correct
22 Correct 63 ms 91540 KB Output is correct
23 Correct 63 ms 90608 KB Output is correct
24 Correct 67 ms 92164 KB Output is correct
25 Correct 66 ms 92620 KB Output is correct
26 Correct 68 ms 92524 KB Output is correct
27 Correct 68 ms 92576 KB Output is correct
28 Correct 67 ms 92620 KB Output is correct
29 Correct 69 ms 92508 KB Output is correct
30 Correct 67 ms 92612 KB Output is correct
31 Correct 74 ms 92620 KB Output is correct
32 Correct 68 ms 92592 KB Output is correct
33 Correct 74 ms 92544 KB Output is correct
34 Correct 74 ms 92548 KB Output is correct
35 Correct 75 ms 90624 KB Output is correct
36 Correct 59 ms 88392 KB Output is correct
37 Correct 84 ms 93412 KB Output is correct
38 Correct 85 ms 93688 KB Output is correct
39 Correct 84 ms 93676 KB Output is correct
40 Correct 83 ms 93644 KB Output is correct
41 Correct 84 ms 93708 KB Output is correct
42 Correct 71 ms 93200 KB Output is correct
43 Correct 70 ms 93092 KB Output is correct
44 Correct 75 ms 93200 KB Output is correct
45 Correct 90 ms 95892 KB Output is correct
46 Correct 89 ms 95908 KB Output is correct
47 Correct 290 ms 146092 KB Output is correct
48 Correct 305 ms 193588 KB Output is correct
49 Correct 329 ms 203540 KB Output is correct
50 Correct 339 ms 215232 KB Output is correct
51 Correct 391 ms 226480 KB Output is correct
52 Correct 400 ms 226516 KB Output is correct
53 Correct 350 ms 224372 KB Output is correct
54 Correct 350 ms 224124 KB Output is correct
55 Correct 344 ms 224128 KB Output is correct
56 Correct 348 ms 225220 KB Output is correct
57 Correct 411 ms 224196 KB Output is correct
58 Correct 411 ms 224596 KB Output is correct
59 Correct 361 ms 224740 KB Output is correct
60 Correct 389 ms 225092 KB Output is correct
61 Correct 354 ms 224868 KB Output is correct
62 Correct 381 ms 227076 KB Output is correct
63 Correct 422 ms 248816 KB Output is correct
64 Correct 429 ms 256596 KB Output is correct
65 Runtime error 379 ms 262144 KB Execution killed with signal 9
66 Halted 0 ms 0 KB -