Submission #389646

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
389646	2021-04-14T10:34:39 Z	milleniumEeee	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	256 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 crt(int pos, int x) {
	if (x == 0) { // wtf
		return;
	}
	int l = pos;
	while (l >= 0) {
		if (l != pos) {
			g[pos].pb({abs(pos - l) / x, l});
		}
		l -= x;
	}
	int r = pos;
	while (r < n) {
		if (r != pos) {
			g[pos].pb({abs(r - pos) / x, r});
		}
		r += x;
	}
}

int dist[MAXN];

signed main() {
	fastInp;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> pos[i] >> p[i];
		crt(pos[i], p[i]);
	}
	
	//for (int i = 1; i <= 1e5; 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

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

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	6476 KB	Output is correct
2	Correct	4 ms	6476 KB	Output is correct
3	Correct	4 ms	6476 KB	Output is correct
4	Correct	4 ms	6476 KB	Output is correct
5	Correct	5 ms	6476 KB	Output is correct
6	Correct	4 ms	6476 KB	Output is correct
7	Correct	4 ms	6476 KB	Output is correct
8	Correct	4 ms	6476 KB	Output is correct
9	Correct	4 ms	6476 KB	Output is correct
10	Correct	4 ms	6604 KB	Output is correct
11	Correct	5 ms	6732 KB	Output is correct
12	Correct	10 ms	9792 KB	Output is correct
13	Correct	9 ms	9748 KB	Output is correct
14	Correct	5 ms	6736 KB	Output is correct
15	Correct	6 ms	6604 KB	Output is correct

Subtask #3
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	6476 KB	Output is correct
2	Correct	4 ms	6476 KB	Output is correct
3	Correct	4 ms	6588 KB	Output is correct
4	Correct	4 ms	6584 KB	Output is correct
5	Correct	4 ms	6476 KB	Output is correct
6	Correct	5 ms	6476 KB	Output is correct
7	Correct	4 ms	6476 KB	Output is correct
8	Correct	5 ms	6588 KB	Output is correct
9	Correct	4 ms	6476 KB	Output is correct
10	Correct	5 ms	6604 KB	Output is correct
11	Correct	5 ms	6848 KB	Output is correct
12	Correct	10 ms	9836 KB	Output is correct
13	Correct	9 ms	9668 KB	Output is correct
14	Correct	4 ms	6732 KB	Output is correct
15	Correct	4 ms	6732 KB	Output is correct
16	Correct	4 ms	6604 KB	Output is correct
17	Correct	5 ms	6988 KB	Output is correct
18	Correct	5 ms	6732 KB	Output is correct
19	Correct	4 ms	6604 KB	Output is correct
20	Correct	79 ms	70684 KB	Output is correct
21	Correct	4 ms	6604 KB	Output is correct
22	Correct	4 ms	6604 KB	Output is correct
23	Correct	4 ms	6732 KB	Output is correct
24	Correct	5 ms	6916 KB	Output is correct
25	Correct	5 ms	6732 KB	Output is correct
26	Correct	98 ms	70976 KB	Output is correct
27	Correct	93 ms	70884 KB	Output is correct
28	Correct	5 ms	6988 KB	Output is correct
29	Correct	6 ms	8012 KB	Output is correct
30	Correct	5 ms	6988 KB	Output is correct
31	Correct	5 ms	7244 KB	Output is correct
32	Correct	6 ms	7120 KB	Output is correct
33	Correct	8 ms	9164 KB	Output is correct
34	Correct	7 ms	9032 KB	Output is correct

Subtask #4
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	6548 KB	Output is correct
2	Correct	4 ms	6476 KB	Output is correct
3	Correct	4 ms	6476 KB	Output is correct
4	Correct	4 ms	6476 KB	Output is correct
5	Correct	4 ms	6476 KB	Output is correct
6	Correct	4 ms	6476 KB	Output is correct
7	Correct	4 ms	6476 KB	Output is correct
8	Correct	4 ms	6476 KB	Output is correct
9	Correct	4 ms	6476 KB	Output is correct
10	Correct	4 ms	6604 KB	Output is correct
11	Correct	6 ms	6732 KB	Output is correct
12	Correct	9 ms	9792 KB	Output is correct
13	Correct	9 ms	9732 KB	Output is correct
14	Correct	4 ms	6744 KB	Output is correct
15	Correct	4 ms	6732 KB	Output is correct
16	Correct	5 ms	6604 KB	Output is correct
17	Correct	5 ms	6992 KB	Output is correct
18	Correct	4 ms	6732 KB	Output is correct
19	Correct	4 ms	6616 KB	Output is correct
20	Correct	76 ms	70784 KB	Output is correct
21	Correct	5 ms	6604 KB	Output is correct
22	Correct	4 ms	6604 KB	Output is correct
23	Correct	5 ms	6732 KB	Output is correct
24	Correct	7 ms	6860 KB	Output is correct
25	Correct	5 ms	6732 KB	Output is correct
26	Correct	97 ms	71008 KB	Output is correct
27	Correct	92 ms	70944 KB	Output is correct
28	Correct	5 ms	7076 KB	Output is correct
29	Correct	7 ms	8020 KB	Output is correct
30	Correct	5 ms	6988 KB	Output is correct
31	Correct	5 ms	7248 KB	Output is correct
32	Correct	5 ms	7116 KB	Output is correct
33	Correct	7 ms	9164 KB	Output is correct
34	Correct	7 ms	9112 KB	Output is correct
35	Correct	13 ms	10012 KB	Output is correct
36	Correct	6 ms	7028 KB	Output is correct
37	Correct	16 ms	13144 KB	Output is correct
38	Correct	17 ms	11852 KB	Output is correct
39	Correct	17 ms	12280 KB	Output is correct
40	Correct	17 ms	12024 KB	Output is correct
41	Correct	16 ms	11844 KB	Output is correct
42	Runtime error	256 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	4 ms	6476 KB	Output is correct
2	Correct	4 ms	6476 KB	Output is correct
3	Correct	4 ms	6476 KB	Output is correct
4	Correct	4 ms	6476 KB	Output is correct
5	Correct	4 ms	6476 KB	Output is correct
6	Correct	4 ms	6476 KB	Output is correct
7	Correct	4 ms	6476 KB	Output is correct
8	Correct	4 ms	6476 KB	Output is correct
9	Correct	4 ms	6476 KB	Output is correct
10	Correct	5 ms	6604 KB	Output is correct
11	Correct	5 ms	6732 KB	Output is correct
12	Correct	9 ms	9796 KB	Output is correct
13	Correct	10 ms	9796 KB	Output is correct
14	Correct	5 ms	6732 KB	Output is correct
15	Correct	5 ms	6732 KB	Output is correct
16	Correct	5 ms	6604 KB	Output is correct
17	Correct	5 ms	6988 KB	Output is correct
18	Correct	5 ms	6732 KB	Output is correct
19	Correct	5 ms	6652 KB	Output is correct
20	Correct	78 ms	70796 KB	Output is correct
21	Correct	4 ms	6604 KB	Output is correct
22	Correct	4 ms	6604 KB	Output is correct
23	Correct	5 ms	6712 KB	Output is correct
24	Correct	5 ms	6860 KB	Output is correct
25	Correct	5 ms	6732 KB	Output is correct
26	Correct	97 ms	71044 KB	Output is correct
27	Correct	93 ms	70944 KB	Output is correct
28	Correct	5 ms	6988 KB	Output is correct
29	Correct	6 ms	8012 KB	Output is correct
30	Correct	5 ms	6988 KB	Output is correct
31	Correct	5 ms	7248 KB	Output is correct
32	Correct	5 ms	7116 KB	Output is correct
33	Correct	7 ms	9164 KB	Output is correct
34	Correct	7 ms	9116 KB	Output is correct
35	Correct	13 ms	9932 KB	Output is correct
36	Correct	5 ms	6988 KB	Output is correct
37	Correct	16 ms	13132 KB	Output is correct
38	Correct	16 ms	11980 KB	Output is correct
39	Correct	20 ms	12236 KB	Output is correct
40	Correct	21 ms	11980 KB	Output is correct
41	Correct	17 ms	11836 KB	Output is correct
42	Runtime error	248 ms	262148 KB	Execution killed with signal 9
43	Halted	0 ms	0 KB	-

Submission #389646

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