oj.uz

Submission #488585

# Submission time Handle Problem Language Result Execution time Memory
488585 2021-11-19T17:46:00 Z pooyashams Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 428 ms 262148 KB 
#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 = 110;
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});
}

priority_queue<pii, vector<pii>, greater<pii>> pq;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m; cin >> m >> n;
	const int sq = 100;
	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);
		}
	}
	fill(dist, dist+maxt, inf);
	dist[pos[0]] = 0;
	pq.push({0, pos[0]});
	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 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 46 ms 90676 KB Output is correct
2 Correct 45 ms 90644 KB Output is correct
3 Correct 46 ms 90832 KB Output is correct
4 Correct 47 ms 90680 KB Output is correct
5 Correct 48 ms 90744 KB Output is correct
6 Correct 45 ms 90676 KB Output is correct
7 Correct 44 ms 90692 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 90656 KB Output is correct
2 Correct 53 ms 90720 KB Output is correct
3 Correct 46 ms 90656 KB Output is correct
4 Correct 46 ms 90732 KB Output is correct
5 Correct 44 ms 90700 KB Output is correct
6 Correct 45 ms 90696 KB Output is correct
7 Correct 44 ms 90732 KB Output is correct
8 Correct 44 ms 90784 KB Output is correct
9 Correct 44 ms 90852 KB Output is correct
10 Correct 44 ms 91092 KB Output is correct
11 Correct 48 ms 91100 KB Output is correct
12 Correct 46 ms 91112 KB Output is correct
13 Correct 44 ms 91084 KB Output is correct
14 Correct 47 ms 91172 KB Output is correct
15 Correct 45 ms 91084 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 90740 KB Output is correct
2 Correct 55 ms 90652 KB Output is correct
3 Correct 46 ms 90728 KB Output is correct
4 Correct 57 ms 90652 KB Output is correct
5 Correct 56 ms 90716 KB Output is correct
6 Correct 43 ms 90692 KB Output is correct
7 Correct 45 ms 90776 KB Output is correct
8 Correct 45 ms 90784 KB Output is correct
9 Correct 57 ms 91000 KB Output is correct
10 Correct 45 ms 91076 KB Output is correct
11 Correct 58 ms 91144 KB Output is correct
12 Correct 56 ms 91128 KB Output is correct
13 Correct 46 ms 91064 KB Output is correct
14 Correct 57 ms 91128 KB Output is correct
15 Correct 48 ms 91168 KB Output is correct
16 Correct 47 ms 91436 KB Output is correct
17 Correct 55 ms 94040 KB Output is correct
18 Correct 72 ms 98816 KB Output is correct
19 Correct 77 ms 99932 KB Output is correct
20 Correct 71 ms 99928 KB Output is correct
21 Correct 49 ms 92416 KB Output is correct
22 Correct 63 ms 98876 KB Output is correct
23 Correct 61 ms 97988 KB Output is correct
24 Correct 70 ms 99472 KB Output is correct
25 Correct 82 ms 99876 KB Output is correct
26 Correct 66 ms 99916 KB Output is correct
27 Correct 67 ms 99876 KB Output is correct
28 Correct 68 ms 99984 KB Output is correct
29 Correct 78 ms 99908 KB Output is correct
30 Correct 69 ms 99908 KB Output is correct
31 Correct 70 ms 99824 KB Output is correct
32 Correct 66 ms 99808 KB Output is correct
33 Correct 73 ms 99920 KB Output is correct
34 Correct 73 ms 99908 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 90640 KB Output is correct
2 Correct 47 ms 90740 KB Output is correct
3 Correct 45 ms 90700 KB Output is correct
4 Correct 44 ms 90748 KB Output is correct
5 Correct 45 ms 90740 KB Output is correct
6 Correct 46 ms 90696 KB Output is correct
7 Correct 45 ms 90680 KB Output is correct
8 Correct 45 ms 90868 KB Output is correct
9 Correct 45 ms 90892 KB Output is correct
10 Correct 45 ms 91060 KB Output is correct
11 Correct 46 ms 91076 KB Output is correct
12 Correct 49 ms 91076 KB Output is correct
13 Correct 46 ms 91076 KB Output is correct
14 Correct 61 ms 91100 KB Output is correct
15 Correct 46 ms 91140 KB Output is correct
16 Correct 47 ms 91456 KB Output is correct
17 Correct 54 ms 94096 KB Output is correct
18 Correct 64 ms 98672 KB Output is correct
19 Correct 65 ms 99856 KB Output is correct
20 Correct 80 ms 99904 KB Output is correct
21 Correct 49 ms 92368 KB Output is correct
22 Correct 68 ms 98796 KB Output is correct
23 Correct 68 ms 97996 KB Output is correct
24 Correct 66 ms 99524 KB Output is correct
25 Correct 65 ms 99960 KB Output is correct
26 Correct 67 ms 99956 KB Output is correct
27 Correct 68 ms 99908 KB Output is correct
28 Correct 65 ms 99988 KB Output is correct
29 Correct 69 ms 99848 KB Output is correct
30 Correct 83 ms 99884 KB Output is correct
31 Correct 66 ms 99844 KB Output is correct
32 Correct 66 ms 99800 KB Output is correct
33 Correct 73 ms 99908 KB Output is correct
34 Correct 72 ms 99968 KB Output is correct
35 Correct 74 ms 98280 KB Output is correct
36 Correct 72 ms 95812 KB Output is correct
37 Correct 90 ms 100996 KB Output is correct
38 Correct 87 ms 101384 KB Output is correct
39 Correct 90 ms 101396 KB Output is correct
40 Correct 90 ms 101316 KB Output is correct
41 Correct 97 ms 101376 KB Output is correct
42 Correct 77 ms 100440 KB Output is correct
43 Correct 67 ms 100456 KB Output is correct
44 Correct 67 ms 100456 KB Output is correct
45 Correct 91 ms 103264 KB Output is correct
46 Correct 89 ms 103200 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 90740 KB Output is correct
2 Correct 47 ms 90704 KB Output is correct
3 Correct 53 ms 90728 KB Output is correct
4 Correct 46 ms 90760 KB Output is correct
5 Correct 51 ms 90792 KB Output is correct
6 Correct 49 ms 90732 KB Output is correct
7 Correct 44 ms 90684 KB Output is correct
8 Correct 43 ms 90760 KB Output is correct
9 Correct 43 ms 90904 KB Output is correct
10 Correct 45 ms 91100 KB Output is correct
11 Correct 61 ms 91080 KB Output is correct
12 Correct 43 ms 91096 KB Output is correct
13 Correct 49 ms 91104 KB Output is correct
14 Correct 55 ms 91076 KB Output is correct
15 Correct 46 ms 91132 KB Output is correct
16 Correct 43 ms 91468 KB Output is correct
17 Correct 51 ms 94064 KB Output is correct
18 Correct 58 ms 98648 KB Output is correct
19 Correct 64 ms 99888 KB Output is correct
20 Correct 67 ms 99864 KB Output is correct
21 Correct 48 ms 92364 KB Output is correct
22 Correct 77 ms 98896 KB Output is correct
23 Correct 75 ms 98036 KB Output is correct
24 Correct 77 ms 99472 KB Output is correct
25 Correct 76 ms 99932 KB Output is correct
26 Correct 80 ms 99936 KB Output is correct
27 Correct 69 ms 99936 KB Output is correct
28 Correct 71 ms 99896 KB Output is correct
29 Correct 95 ms 99936 KB Output is correct
30 Correct 83 ms 99800 KB Output is correct
31 Correct 69 ms 99888 KB Output is correct
32 Correct 69 ms 99868 KB Output is correct
33 Correct 76 ms 99920 KB Output is correct
34 Correct 101 ms 99964 KB Output is correct
35 Correct 78 ms 98212 KB Output is correct
36 Correct 60 ms 95812 KB Output is correct
37 Correct 91 ms 100988 KB Output is correct
38 Correct 95 ms 101308 KB Output is correct
39 Correct 91 ms 101316 KB Output is correct
40 Correct 93 ms 101412 KB Output is correct
41 Correct 95 ms 101268 KB Output is correct
42 Correct 90 ms 100416 KB Output is correct
43 Correct 74 ms 100448 KB Output is correct
44 Correct 73 ms 100456 KB Output is correct
45 Correct 93 ms 103256 KB Output is correct
46 Correct 96 ms 103284 KB Output is correct
47 Correct 339 ms 153420 KB Output is correct
48 Correct 319 ms 200456 KB Output is correct
49 Correct 328 ms 210244 KB Output is correct
50 Correct 323 ms 221696 KB Output is correct
51 Correct 415 ms 233156 KB Output is correct
52 Correct 394 ms 233276 KB Output is correct
53 Correct 380 ms 231304 KB Output is correct
54 Correct 335 ms 229972 KB Output is correct
55 Correct 338 ms 229980 KB Output is correct
56 Correct 346 ms 231464 KB Output is correct
57 Correct 428 ms 230216 KB Output is correct
58 Correct 356 ms 230760 KB Output is correct
59 Correct 363 ms 230968 KB Output is correct
60 Correct 385 ms 231348 KB Output is correct
61 Correct 382 ms 231236 KB Output is correct
62 Correct 387 ms 233928 KB Output is correct
63 Correct 421 ms 255052 KB Output is correct
64 Runtime error 350 ms 262148 KB Execution killed with signal 9
65 Halted 0 ms 0 KB -