Submission #488583

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
488583	2021-11-19T17:26:36 Z	pooyashams	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	275 ms	262148 KB

skyscraper

#include <algorithm>
#include <iostream>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 3e4+10;
const int mxsq = 210;
const int maxt = maxn*mxsq;
const int inf = 1e9+7;

int len[maxn];
int pos[maxn];
int dist[maxt];
vector<pii> G[maxt];

inline void add_edge(int a, int b, int w, bool nd)
{
	G[a].push_back({w, b});
	if(nd)
		G[b].push_back({w, a});
}

inline void dijkstra(int s)
{
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	fill(dist, dist+maxt, inf);
	dist[s] = 0;
	pq.push({0, s});
	while(!pq.empty())
	{
		int t = pq.top().second; 
		int d = pq.top().first;
		pq.pop();
		for(pii e: G[t])
		{
			int u = e.second;
			int w = d+e.first;
			if(dist[u] <= w)
				continue;
			dist[u] = w;
			pq.push({dist[u], u});
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m; cin >> m >> n;
	const int sq = 200;
	for(int p = 1; p < sq; p++)
	{
		for(int i = 0; i < m; i++)
		{
			if(i + p < m)
				add_edge(p*m+i, p*m+i+p, 1, true);
			add_edge(p*m+i, i, 0, false);
		}
	}
	for(int i = 0; i < n; i++)
	{
		cin >> pos[i] >> len[i];
		int b = pos[i];
		int p = len[i];
		if(p >= sq)
		{
			for(int j = b%p; j < m; j += p)
			{
				add_edge(b, j, abs(b-j)/p, false);
			}
		}
		else
		{
			add_edge(b, p*m+b, 0, false);
		}
	}
	dijkstra(pos[0]);
	int x = dist[pos[1]];
	if(x == inf) x = -1;
	cout << x << endl;
	return 0;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	83 ms	172868 KB	Output is correct
2	Correct	80 ms	172932 KB	Output is correct
3	Correct	81 ms	172968 KB	Output is correct
4	Correct	80 ms	172900 KB	Output is correct
5	Correct	84 ms	172916 KB	Output is correct
6	Correct	96 ms	172924 KB	Output is correct
7	Correct	80 ms	172976 KB	Output is correct

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	80 ms	172952 KB	Output is correct
2	Correct	82 ms	172896 KB	Output is correct
3	Correct	101 ms	172884 KB	Output is correct
4	Correct	85 ms	173020 KB	Output is correct
5	Correct	80 ms	172928 KB	Output is correct
6	Correct	80 ms	172992 KB	Output is correct
7	Correct	79 ms	173000 KB	Output is correct
8	Correct	106 ms	173172 KB	Output is correct
9	Correct	84 ms	173244 KB	Output is correct
10	Correct	86 ms	173644 KB	Output is correct
11	Correct	81 ms	173592 KB	Output is correct
12	Correct	80 ms	173588 KB	Output is correct
13	Correct	100 ms	173600 KB	Output is correct
14	Correct	84 ms	173592 KB	Output is correct
15	Correct	83 ms	173624 KB	Output is correct

Subtask #3

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	83 ms	172868 KB	Output is correct
2	Correct	80 ms	172900 KB	Output is correct
3	Correct	80 ms	172968 KB	Output is correct
4	Correct	81 ms	172996 KB	Output is correct
5	Correct	81 ms	172912 KB	Output is correct
6	Correct	93 ms	172996 KB	Output is correct
7	Correct	85 ms	172972 KB	Output is correct
8	Correct	81 ms	173184 KB	Output is correct
9	Correct	81 ms	173260 KB	Output is correct
10	Correct	82 ms	173624 KB	Output is correct
11	Correct	83 ms	173704 KB	Output is correct
12	Correct	82 ms	173612 KB	Output is correct
13	Correct	90 ms	173660 KB	Output is correct
14	Correct	83 ms	173612 KB	Output is correct
15	Correct	78 ms	173708 KB	Output is correct
16	Correct	86 ms	174368 KB	Output is correct
17	Correct	111 ms	179284 KB	Output is correct
18	Correct	113 ms	188684 KB	Output is correct
19	Correct	120 ms	190992 KB	Output is correct
20	Correct	121 ms	191108 KB	Output is correct
21	Correct	91 ms	175980 KB	Output is correct
22	Correct	113 ms	188996 KB	Output is correct
23	Correct	110 ms	187212 KB	Output is correct
24	Correct	132 ms	190260 KB	Output is correct
25	Correct	121 ms	191108 KB	Output is correct
26	Correct	131 ms	190972 KB	Output is correct
27	Correct	122 ms	191000 KB	Output is correct
28	Correct	122 ms	191044 KB	Output is correct
29	Correct	121 ms	191008 KB	Output is correct
30	Correct	119 ms	190916 KB	Output is correct
31	Correct	150 ms	191044 KB	Output is correct
32	Correct	126 ms	190944 KB	Output is correct
33	Correct	132 ms	191036 KB	Output is correct
34	Correct	129 ms	191112 KB	Output is correct

Subtask #4

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	80 ms	172992 KB	Output is correct
2	Correct	81 ms	172884 KB	Output is correct
3	Correct	80 ms	172888 KB	Output is correct
4	Correct	85 ms	173040 KB	Output is correct
5	Correct	81 ms	172948 KB	Output is correct
6	Correct	80 ms	173000 KB	Output is correct
7	Correct	84 ms	172968 KB	Output is correct
8	Correct	97 ms	173116 KB	Output is correct
9	Correct	80 ms	173252 KB	Output is correct
10	Correct	83 ms	173640 KB	Output is correct
11	Correct	93 ms	173592 KB	Output is correct
12	Correct	84 ms	173612 KB	Output is correct
13	Correct	82 ms	173636 KB	Output is correct
14	Correct	82 ms	173628 KB	Output is correct
15	Correct	85 ms	173696 KB	Output is correct
16	Correct	87 ms	174320 KB	Output is correct
17	Correct	100 ms	179360 KB	Output is correct
18	Correct	115 ms	188636 KB	Output is correct
19	Correct	128 ms	191044 KB	Output is correct
20	Correct	118 ms	191020 KB	Output is correct
21	Correct	90 ms	175996 KB	Output is correct
22	Correct	117 ms	188960 KB	Output is correct
23	Correct	112 ms	187332 KB	Output is correct
24	Correct	125 ms	190092 KB	Output is correct
25	Correct	127 ms	191188 KB	Output is correct
26	Correct	133 ms	190976 KB	Output is correct
27	Correct	136 ms	191020 KB	Output is correct
28	Correct	126 ms	191096 KB	Output is correct
29	Correct	148 ms	191044 KB	Output is correct
30	Correct	128 ms	190920 KB	Output is correct
31	Correct	126 ms	191084 KB	Output is correct
32	Correct	135 ms	191032 KB	Output is correct
33	Correct	127 ms	191044 KB	Output is correct
34	Correct	138 ms	191084 KB	Output is correct
35	Correct	159 ms	186620 KB	Output is correct
36	Correct	104 ms	182572 KB	Output is correct
37	Correct	159 ms	191704 KB	Output is correct
38	Correct	190 ms	192228 KB	Output is correct
39	Correct	155 ms	192264 KB	Output is correct
40	Correct	155 ms	192368 KB	Output is correct
41	Correct	150 ms	192312 KB	Output is correct
42	Correct	122 ms	191572 KB	Output is correct
43	Correct	164 ms	191560 KB	Output is correct
44	Correct	125 ms	191560 KB	Output is correct
45	Correct	172 ms	193156 KB	Output is correct
46	Correct	186 ms	193320 KB	Output is correct

Subtask #5

0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	91 ms	172924 KB	Output is correct
2	Correct	95 ms	172892 KB	Output is correct
3	Correct	80 ms	172900 KB	Output is correct
4	Correct	82 ms	173008 KB	Output is correct
5	Correct	81 ms	173048 KB	Output is correct
6	Correct	83 ms	172936 KB	Output is correct
7	Correct	91 ms	172996 KB	Output is correct
8	Correct	84 ms	173124 KB	Output is correct
9	Correct	92 ms	173272 KB	Output is correct
10	Correct	83 ms	173636 KB	Output is correct
11	Correct	107 ms	173704 KB	Output is correct
12	Correct	82 ms	173580 KB	Output is correct
13	Correct	85 ms	173600 KB	Output is correct
14	Correct	81 ms	173596 KB	Output is correct
15	Correct	83 ms	173704 KB	Output is correct
16	Correct	97 ms	174284 KB	Output is correct
17	Correct	101 ms	179248 KB	Output is correct
18	Correct	129 ms	188612 KB	Output is correct
19	Correct	147 ms	190988 KB	Output is correct
20	Correct	118 ms	191108 KB	Output is correct
21	Correct	89 ms	176028 KB	Output is correct
22	Correct	116 ms	188924 KB	Output is correct
23	Correct	131 ms	187220 KB	Output is correct
24	Correct	119 ms	190188 KB	Output is correct
25	Correct	127 ms	191108 KB	Output is correct
26	Correct	137 ms	191092 KB	Output is correct
27	Correct	129 ms	191000 KB	Output is correct
28	Correct	127 ms	191140 KB	Output is correct
29	Correct	130 ms	191036 KB	Output is correct
30	Correct	137 ms	190980 KB	Output is correct
31	Correct	125 ms	190948 KB	Output is correct
32	Correct	124 ms	191020 KB	Output is correct
33	Correct	126 ms	191044 KB	Output is correct
34	Correct	129 ms	191020 KB	Output is correct
35	Correct	134 ms	186660 KB	Output is correct
36	Correct	104 ms	182612 KB	Output is correct
37	Correct	167 ms	191624 KB	Output is correct
38	Correct	166 ms	192272 KB	Output is correct
39	Correct	150 ms	192344 KB	Output is correct
40	Correct	172 ms	192252 KB	Output is correct
41	Correct	157 ms	192252 KB	Output is correct
42	Correct	128 ms	191568 KB	Output is correct
43	Correct	124 ms	191552 KB	Output is correct
44	Correct	125 ms	191524 KB	Output is correct
45	Correct	178 ms	193244 KB	Output is correct
46	Correct	168 ms	193272 KB	Output is correct
47	Runtime error	275 ms	262148 KB	Execution killed with signal 9
48	Halted	0 ms	0 KB	-