답안 #389641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
389641	2021-04-14T10:29:46 Z	milleniumEeee	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	253 ms	262148 KB

skyscraper

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long
using namespace std;

const int MAXN = (int)2e5 + 5;
const int INF = 1e18;

int pos[MAXN], p[MAXN];
vector <pii> g[MAXN];

int n, m;
void create(int pos, int x) {
	if (x == 0) { // wtf
		return;
	}
	for (int i = pos % x; i < n; i += x) {
		if (i != pos) {
			g[pos].pb({abs(pos - i) / x, i});
		}
	}
}

int dist[MAXN];

signed main() {
	fastInp;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> pos[i] >> p[i];
		create(pos[i], p[i]);
	}
	
	for (int i = 1; i <= 5000; i++) {
		cerr << "ok" << endl;
	}
	
	memset(dist, -1, sizeof(dist));
	dist[pos[0]] = 0;
	queue <pii> pq;
	pq.push({0, pos[0]});
	while (!pq.empty()) {
		int v = pq.front().sc;
		int cost = -pq.front().fr;
		pq.pop();
		if (cost > dist[v]) {
			continue;
		}
		for (auto el : g[v]) {
			int c = el.fr, to = el.sc;
			if (dist[to] == -1 || dist[to] > dist[v] + c) {
				dist[to] = dist[v] + c;
				pq.push({-dist[to], to});
			}
		}
	}
	cout << dist[pos[1]] << endl;
}
/*
4 4
1 1
0 1
3 4
2 0
*/

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	6604 KB	Output is correct
2	Correct	21 ms	6576 KB	Output is correct
3	Correct	19 ms	6576 KB	Output is correct
4	Correct	19 ms	6576 KB	Output is correct
5	Correct	19 ms	6568 KB	Output is correct
6	Correct	19 ms	6476 KB	Output is correct
7	Correct	19 ms	6580 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	6604 KB	Output is correct
2	Correct	19 ms	6580 KB	Output is correct
3	Correct	22 ms	6560 KB	Output is correct
4	Correct	19 ms	6576 KB	Output is correct
5	Correct	20 ms	6580 KB	Output is correct
6	Correct	19 ms	6572 KB	Output is correct
7	Correct	19 ms	6480 KB	Output is correct
8	Correct	19 ms	6604 KB	Output is correct
9	Correct	19 ms	6604 KB	Output is correct
10	Correct	19 ms	6632 KB	Output is correct
11	Correct	20 ms	6860 KB	Output is correct
12	Correct	24 ms	9824 KB	Output is correct
13	Correct	26 ms	9780 KB	Output is correct
14	Correct	20 ms	6720 KB	Output is correct
15	Correct	20 ms	6716 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	6580 KB	Output is correct
2	Correct	23 ms	6572 KB	Output is correct
3	Correct	19 ms	6604 KB	Output is correct
4	Correct	21 ms	6568 KB	Output is correct
5	Correct	21 ms	6572 KB	Output is correct
6	Correct	19 ms	6476 KB	Output is correct
7	Correct	19 ms	6568 KB	Output is correct
8	Correct	19 ms	6572 KB	Output is correct
9	Correct	19 ms	6580 KB	Output is correct
10	Correct	20 ms	6628 KB	Output is correct
11	Correct	20 ms	6860 KB	Output is correct
12	Correct	24 ms	9792 KB	Output is correct
13	Correct	25 ms	9764 KB	Output is correct
14	Correct	20 ms	6732 KB	Output is correct
15	Correct	20 ms	6720 KB	Output is correct
16	Correct	20 ms	6704 KB	Output is correct
17	Correct	20 ms	7116 KB	Output is correct
18	Correct	20 ms	6732 KB	Output is correct
19	Correct	20 ms	6684 KB	Output is correct
20	Correct	91 ms	70732 KB	Output is correct
21	Correct	20 ms	6624 KB	Output is correct
22	Correct	20 ms	6700 KB	Output is correct
23	Correct	20 ms	6716 KB	Output is correct
24	Correct	21 ms	6860 KB	Output is correct
25	Correct	20 ms	6732 KB	Output is correct
26	Correct	122 ms	71048 KB	Output is correct
27	Correct	109 ms	70832 KB	Output is correct
28	Correct	20 ms	6988 KB	Output is correct
29	Correct	21 ms	8012 KB	Output is correct
30	Correct	20 ms	6988 KB	Output is correct
31	Correct	20 ms	7372 KB	Output is correct
32	Correct	20 ms	7064 KB	Output is correct
33	Correct	24 ms	9160 KB	Output is correct
34	Correct	23 ms	9108 KB	Output is correct

Subtask #4
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	6604 KB	Output is correct
2	Correct	20 ms	6576 KB	Output is correct
3	Correct	19 ms	6576 KB	Output is correct
4	Correct	20 ms	6568 KB	Output is correct
5	Correct	19 ms	6576 KB	Output is correct
6	Correct	19 ms	6568 KB	Output is correct
7	Correct	21 ms	6576 KB	Output is correct
8	Correct	22 ms	6604 KB	Output is correct
9	Correct	20 ms	6604 KB	Output is correct
10	Correct	20 ms	6732 KB	Output is correct
11	Correct	20 ms	6828 KB	Output is correct
12	Correct	25 ms	9752 KB	Output is correct
13	Correct	25 ms	9796 KB	Output is correct
14	Correct	20 ms	6724 KB	Output is correct
15	Correct	20 ms	6732 KB	Output is correct
16	Correct	19 ms	6732 KB	Output is correct
17	Correct	20 ms	7072 KB	Output is correct
18	Correct	19 ms	6732 KB	Output is correct
19	Correct	19 ms	6684 KB	Output is correct
20	Correct	90 ms	70772 KB	Output is correct
21	Correct	20 ms	6636 KB	Output is correct
22	Correct	20 ms	6700 KB	Output is correct
23	Correct	20 ms	6720 KB	Output is correct
24	Correct	21 ms	6860 KB	Output is correct
25	Correct	21 ms	6752 KB	Output is correct
26	Correct	113 ms	71028 KB	Output is correct
27	Correct	110 ms	70908 KB	Output is correct
28	Correct	24 ms	7056 KB	Output is correct
29	Correct	21 ms	8012 KB	Output is correct
30	Correct	20 ms	6988 KB	Output is correct
31	Correct	20 ms	7320 KB	Output is correct
32	Correct	20 ms	7064 KB	Output is correct
33	Correct	25 ms	9240 KB	Output is correct
34	Correct	24 ms	9032 KB	Output is correct
35	Correct	27 ms	9980 KB	Output is correct
36	Correct	21 ms	6988 KB	Output is correct
37	Correct	30 ms	13184 KB	Output is correct
38	Correct	31 ms	11980 KB	Output is correct
39	Correct	32 ms	12340 KB	Output is correct
40	Correct	32 ms	12484 KB	Output is correct
41	Correct	33 ms	12196 KB	Output is correct
42	Runtime error	252 ms	262148 KB	Execution killed with signal 9
43	Halted	0 ms	0 KB	-

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	6604 KB	Output is correct
2	Correct	19 ms	6568 KB	Output is correct
3	Correct	19 ms	6568 KB	Output is correct
4	Correct	19 ms	6564 KB	Output is correct
5	Correct	19 ms	6604 KB	Output is correct
6	Correct	19 ms	6572 KB	Output is correct
7	Correct	19 ms	6476 KB	Output is correct
8	Correct	19 ms	6588 KB	Output is correct
9	Correct	19 ms	6580 KB	Output is correct
10	Correct	19 ms	6604 KB	Output is correct
11	Correct	21 ms	6860 KB	Output is correct
12	Correct	25 ms	9832 KB	Output is correct
13	Correct	28 ms	9796 KB	Output is correct
14	Correct	19 ms	6732 KB	Output is correct
15	Correct	20 ms	6720 KB	Output is correct
16	Correct	19 ms	6732 KB	Output is correct
17	Correct	20 ms	7088 KB	Output is correct
18	Correct	20 ms	6732 KB	Output is correct
19	Correct	19 ms	6680 KB	Output is correct
20	Correct	93 ms	70880 KB	Output is correct
21	Correct	20 ms	6628 KB	Output is correct
22	Correct	19 ms	6700 KB	Output is correct
23	Correct	20 ms	6720 KB	Output is correct
24	Correct	20 ms	6860 KB	Output is correct
25	Correct	20 ms	6752 KB	Output is correct
26	Correct	112 ms	71028 KB	Output is correct
27	Correct	110 ms	70892 KB	Output is correct
28	Correct	25 ms	7072 KB	Output is correct
29	Correct	22 ms	8012 KB	Output is correct
30	Correct	20 ms	6988 KB	Output is correct
31	Correct	20 ms	7308 KB	Output is correct
32	Correct	20 ms	7116 KB	Output is correct
33	Correct	22 ms	9164 KB	Output is correct
34	Correct	22 ms	9096 KB	Output is correct
35	Correct	28 ms	9924 KB	Output is correct
36	Correct	21 ms	6988 KB	Output is correct
37	Correct	31 ms	13164 KB	Output is correct
38	Correct	32 ms	11972 KB	Output is correct
39	Correct	35 ms	12428 KB	Output is correct
40	Correct	32 ms	12480 KB	Output is correct
41	Correct	32 ms	12196 KB	Output is correct
42	Runtime error	253 ms	262148 KB	Execution killed with signal 9
43	Halted	0 ms	0 KB	-

답안 #389641

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 14.0 / 14.0

Subtask #4 0 / 21.0

Subtask #5 0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
14.0 / 14.0

Subtask #4
0 / 21.0

Subtask #5
0 / 43.0