oj.uz

Submission #488569

# Submission time Handle Problem Language Result Execution time Memory
488569 2021-11-19T16:44:30 Z pooyashams Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 163 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;
typedef pair<ll, int> pli;

const int maxn = 3e4+10;
const int mxsq = 210;
const int maxt = maxn*mxsq;
const ll inf = 1e16;

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

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

inline void dijkstra(int s)
{
	set<pli> pq;
	fill(dist, dist+maxt, inf);
	auto mark = [&](int v, ll d)
	{
		if(dist[v] <= d) return;
		pq.erase({dist[v], v});
		dist[v] = d;
		pq.insert({dist[v], v});
	};
	mark(s, 0);
	while(!pq.empty())
	{
		int t = pq.begin()->second;
		ll d = pq.begin()->first;
		pq.erase(pq.begin());
		for(pli e: G[t])
		{
			int u = e.second;
			ll w = e.first;
			mark(u, d+w);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m; cin >> m >> n;
	const int sq = 1;
	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]);
	ll 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 86 ms 197572 KB Output is correct
2 Correct 92 ms 197568 KB Output is correct
3 Correct 93 ms 197628 KB Output is correct
4 Correct 99 ms 197728 KB Output is correct
5 Correct 86 ms 197496 KB Output is correct
6 Correct 85 ms 197624 KB Output is correct
7 Correct 85 ms 197520 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 197572 KB Output is correct
2 Correct 86 ms 197716 KB Output is correct
3 Correct 88 ms 197632 KB Output is correct
4 Correct 86 ms 197572 KB Output is correct
5 Correct 87 ms 197532 KB Output is correct
6 Correct 96 ms 197540 KB Output is correct
7 Correct 87 ms 197572 KB Output is correct
8 Correct 89 ms 197700 KB Output is correct
9 Correct 87 ms 197560 KB Output is correct
10 Correct 89 ms 197572 KB Output is correct
11 Correct 87 ms 197828 KB Output is correct
12 Correct 106 ms 200804 KB Output is correct
13 Correct 93 ms 200892 KB Output is correct
14 Correct 91 ms 197728 KB Output is correct
15 Correct 85 ms 197756 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 197584 KB Output is correct
2 Correct 86 ms 197608 KB Output is correct
3 Correct 89 ms 197572 KB Output is correct
4 Correct 95 ms 197552 KB Output is correct
5 Correct 92 ms 197532 KB Output is correct
6 Correct 86 ms 197576 KB Output is correct
7 Correct 86 ms 197572 KB Output is correct
8 Correct 85 ms 197572 KB Output is correct
9 Correct 87 ms 197544 KB Output is correct
10 Correct 92 ms 197704 KB Output is correct
11 Correct 95 ms 197832 KB Output is correct
12 Correct 89 ms 200896 KB Output is correct
13 Correct 90 ms 200784 KB Output is correct
14 Correct 93 ms 197768 KB Output is correct
15 Correct 90 ms 197700 KB Output is correct
16 Correct 89 ms 197704 KB Output is correct
17 Correct 92 ms 198144 KB Output is correct
18 Correct 86 ms 197708 KB Output is correct
19 Correct 94 ms 197652 KB Output is correct
20 Correct 152 ms 261848 KB Output is correct
21 Correct 85 ms 197708 KB Output is correct
22 Correct 90 ms 197680 KB Output is correct
23 Correct 87 ms 197828 KB Output is correct
24 Correct 91 ms 198000 KB Output is correct
25 Correct 99 ms 197956 KB Output is correct
26 Correct 163 ms 254260 KB Output is correct
27 Correct 157 ms 250964 KB Output is correct
28 Correct 88 ms 198144 KB Output is correct
29 Correct 90 ms 199052 KB Output is correct
30 Correct 102 ms 198104 KB Output is correct
31 Correct 90 ms 198420 KB Output is correct
32 Correct 89 ms 198204 KB Output is correct
33 Correct 92 ms 200260 KB Output is correct
34 Correct 92 ms 200112 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 197532 KB Output is correct
2 Correct 110 ms 197608 KB Output is correct
3 Correct 94 ms 197532 KB Output is correct
4 Correct 86 ms 197628 KB Output is correct
5 Correct 86 ms 197572 KB Output is correct
6 Correct 87 ms 197604 KB Output is correct
7 Correct 86 ms 197624 KB Output is correct
8 Correct 91 ms 197656 KB Output is correct
9 Correct 89 ms 197552 KB Output is correct
10 Correct 88 ms 197572 KB Output is correct
11 Correct 87 ms 197920 KB Output is correct
12 Correct 92 ms 200888 KB Output is correct
13 Correct 90 ms 200792 KB Output is correct
14 Correct 88 ms 197816 KB Output is correct
15 Correct 86 ms 197736 KB Output is correct
16 Correct 86 ms 197740 KB Output is correct
17 Correct 87 ms 198200 KB Output is correct
18 Correct 86 ms 197708 KB Output is correct
19 Correct 87 ms 197736 KB Output is correct
20 Correct 151 ms 261900 KB Output is correct
21 Correct 91 ms 197692 KB Output is correct
22 Correct 87 ms 197744 KB Output is correct
23 Correct 99 ms 197736 KB Output is correct
24 Correct 87 ms 198020 KB Output is correct
25 Correct 92 ms 197872 KB Output is correct
26 Correct 160 ms 254276 KB Output is correct
27 Correct 157 ms 250916 KB Output is correct
28 Correct 86 ms 198112 KB Output is correct
29 Correct 90 ms 198988 KB Output is correct
30 Correct 89 ms 198072 KB Output is correct
31 Correct 89 ms 198340 KB Output is correct
32 Correct 100 ms 198152 KB Output is correct
33 Correct 90 ms 200256 KB Output is correct
34 Correct 93 ms 200084 KB Output is correct
35 Correct 98 ms 201720 KB Output is correct
36 Correct 88 ms 198176 KB Output is correct
37 Correct 106 ms 204660 KB Output is correct
38 Correct 98 ms 203700 KB Output is correct
39 Correct 108 ms 204100 KB Output is correct
40 Correct 102 ms 203920 KB Output is correct
41 Correct 98 ms 203716 KB Output is correct
42 Runtime error 153 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 90 ms 197524 KB Output is correct
2 Correct 86 ms 197572 KB Output is correct
3 Correct 93 ms 197516 KB Output is correct
4 Correct 84 ms 197540 KB Output is correct
5 Correct 96 ms 197516 KB Output is correct
6 Correct 87 ms 197572 KB Output is correct
7 Correct 96 ms 197564 KB Output is correct
8 Correct 88 ms 197572 KB Output is correct
9 Correct 93 ms 197592 KB Output is correct
10 Correct 88 ms 197660 KB Output is correct
11 Correct 90 ms 197828 KB Output is correct
12 Correct 101 ms 200808 KB Output is correct
13 Correct 105 ms 200792 KB Output is correct
14 Correct 93 ms 197840 KB Output is correct
15 Correct 87 ms 197828 KB Output is correct
16 Correct 86 ms 197780 KB Output is correct
17 Correct 89 ms 198092 KB Output is correct
18 Correct 86 ms 197696 KB Output is correct
19 Correct 86 ms 197684 KB Output is correct
20 Correct 154 ms 261880 KB Output is correct
21 Correct 87 ms 197616 KB Output is correct
22 Correct 87 ms 197700 KB Output is correct
23 Correct 87 ms 197812 KB Output is correct
24 Correct 88 ms 198020 KB Output is correct
25 Correct 91 ms 197872 KB Output is correct
26 Correct 160 ms 254328 KB Output is correct
27 Correct 156 ms 250956 KB Output is correct
28 Correct 87 ms 198156 KB Output is correct
29 Correct 88 ms 199000 KB Output is correct
30 Correct 91 ms 198156 KB Output is correct
31 Correct 87 ms 198348 KB Output is correct
32 Correct 85 ms 198212 KB Output is correct
33 Correct 91 ms 200268 KB Output is correct
34 Correct 90 ms 200144 KB Output is correct
35 Correct 98 ms 201800 KB Output is correct
36 Correct 88 ms 198160 KB Output is correct
37 Correct 96 ms 204740 KB Output is correct
38 Correct 100 ms 203684 KB Output is correct
39 Correct 98 ms 204112 KB Output is correct
40 Correct 96 ms 203816 KB Output is correct
41 Correct 98 ms 203756 KB Output is correct
42 Runtime error 153 ms 262148 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -