oj.uz

Submission #1114111

# Submission time Handle Problem Language Result Execution time Memory
1114111 2024-11-18T08:03:39 Z raspy Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 193636 KB 
#include <bits/stdc++.h>
 
#define int long long
#define vi vector<int>
#define ii pair<int, int>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define P 31
#define mod 1'000'000'007
#define inf 1'000'000'000'000
#define pb push_back
#define str string
#define sz(x) (x).size()
#define vvi vector<vi>
#define fun function
#define oopt cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
#define file freopen("problemname.in", "r", stdin); freopen("pr.out", "w", stdout);
#define dbg(v) cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;
 
using namespace std;
template <class T, int SZ> using arr = array<T, SZ>;
 
int b[30001];
int power[30001];
set<int> pravi[30001];
set<ii> graf[30001];
int ob[30001];
int obp[201][30001];

void solve()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < 30001; i++)
	{
		ob[i] = inf;
		for (int j = 0; j < 201; j++)
			obp[j][i] = inf;
	}
	for (int i = 0; i < m; i++)
	{
		cin >> b[i] >> power[i];
		if (power[i] > 200)
		{
			for (int j = 1; j*j <= n; j++)
			{
				if (b[i]+power[i]*j < n)
					graf[b[i]].insert({b[i]+power[i]*j, j});
				if (b[i]-power[i]*j >= 0)
					graf[b[i]].insert({b[i]-power[i]*j, j});
			}
		}
		else
		{
			pravi[b[i]].insert(power[i]);
		}
	}
	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
	if (power[0] > 200)
	{
		pq.push({0, b[0], -1});
		ob[b[0]] = 0;
	}
	else
	{
		pq.push({0, b[0], power[0]});
		obp[power[0]][b[0]] = 0;
	}
	while (pq.size())
	{
		auto [d, pos, pow] = pq.top();
		pq.pop();
		if (pos == b[1])
		{
			cout << d << "\n";
			return;
		}
		if (pow > 200 || pow == -1)
		{
			if (ob[pos] < d) continue;
			for (auto [p, w] : graf[pos])
			{
				if (ob[p] > d+w)
				{
					ob[p] = d+w;
					pq.push({d+w, p, -1});
				}
			}
			for (int p : pravi[pos])
			{
				if (obp[p][pos] > d)
				{
					obp[p][pos] = d;
					pq.push({d, pos, p});
				}
			}
		}
		else
		{
			if (obp[pow][pos] < d) continue;
			if (pos-pow >= 0 && obp[pow][pos-pow] > d+1)
			{
				obp[pow][pos-pow] = d+1;
				pq.push({d+1, pos-pow, pow});
			}
			if (pos+pow < n && obp[pow][pos+pow] > d+1)
			{
				obp[pow][pos+pow] = d+1;
				pq.push({d+1, pos+pow, pow});
			}
			if (ob[pos] > d)
			{
				ob[pos] = d;
				pq.push({d, pos, -1});
			}
			for (int p : pravi[pos])
			{
				if (obp[p][pos] > d)
				{
					obp[p][pos] = d;
					pq.push({d, pos, p});
				}
			}
		}
	}
	cout << -1 << "\n";
}

signed main()
{
	oopt;
	int t = 1;
	// cin >> t;
	while (t--)
		solve();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 50512 KB Output is correct
2 Correct 9 ms 50512 KB Output is correct
3 Correct 11 ms 50512 KB Output is correct
4 Correct 12 ms 50512 KB Output is correct
5 Correct 20 ms 50524 KB Output is correct
6 Correct 17 ms 50512 KB Output is correct
7 Correct 20 ms 50512 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 50512 KB Output is correct
2 Correct 12 ms 50512 KB Output is correct
3 Correct 22 ms 50512 KB Output is correct
4 Correct 22 ms 50668 KB Output is correct
5 Correct 21 ms 50512 KB Output is correct
6 Correct 21 ms 50656 KB Output is correct
7 Correct 22 ms 50512 KB Output is correct
8 Correct 21 ms 50512 KB Output is correct
9 Correct 19 ms 50512 KB Output is correct
10 Correct 19 ms 50504 KB Output is correct
11 Correct 20 ms 50768 KB Output is correct
12 Correct 20 ms 50592 KB Output is correct
13 Correct 19 ms 50512 KB Output is correct
14 Correct 19 ms 50764 KB Output is correct
15 Correct 22 ms 50768 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 50512 KB Output is correct
2 Correct 20 ms 50676 KB Output is correct
3 Correct 20 ms 50488 KB Output is correct
4 Correct 19 ms 50512 KB Output is correct
5 Correct 25 ms 50460 KB Output is correct
6 Correct 22 ms 50512 KB Output is correct
7 Correct 23 ms 50512 KB Output is correct
8 Correct 17 ms 50512 KB Output is correct
9 Correct 20 ms 50512 KB Output is correct
10 Correct 20 ms 50768 KB Output is correct
11 Correct 20 ms 50768 KB Output is correct
12 Correct 22 ms 50512 KB Output is correct
13 Correct 20 ms 50512 KB Output is correct
14 Correct 24 ms 50764 KB Output is correct
15 Correct 26 ms 50752 KB Output is correct
16 Correct 23 ms 50780 KB Output is correct
17 Correct 23 ms 50936 KB Output is correct
18 Correct 27 ms 50804 KB Output is correct
19 Correct 25 ms 50768 KB Output is correct
20 Correct 27 ms 50892 KB Output is correct
21 Correct 27 ms 50768 KB Output is correct
22 Correct 26 ms 50652 KB Output is correct
23 Correct 26 ms 50768 KB Output is correct
24 Correct 31 ms 50760 KB Output is correct
25 Correct 24 ms 50928 KB Output is correct
26 Correct 22 ms 50760 KB Output is correct
27 Correct 22 ms 50628 KB Output is correct
28 Correct 24 ms 50768 KB Output is correct
29 Correct 26 ms 50760 KB Output is correct
30 Correct 14 ms 50512 KB Output is correct
31 Correct 27 ms 50760 KB Output is correct
32 Correct 29 ms 50768 KB Output is correct
33 Correct 25 ms 50768 KB Output is correct
34 Correct 16 ms 50768 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 50512 KB Output is correct
2 Correct 9 ms 50680 KB Output is correct
3 Correct 20 ms 50520 KB Output is correct
4 Correct 23 ms 50512 KB Output is correct
5 Correct 26 ms 50608 KB Output is correct
6 Correct 26 ms 50508 KB Output is correct
7 Correct 29 ms 50520 KB Output is correct
8 Correct 26 ms 50632 KB Output is correct
9 Correct 25 ms 50512 KB Output is correct
10 Correct 27 ms 50668 KB Output is correct
11 Correct 29 ms 50940 KB Output is correct
12 Correct 31 ms 50512 KB Output is correct
13 Correct 29 ms 50512 KB Output is correct
14 Correct 32 ms 50760 KB Output is correct
15 Correct 29 ms 50768 KB Output is correct
16 Correct 26 ms 50768 KB Output is correct
17 Correct 30 ms 50852 KB Output is correct
18 Correct 33 ms 50632 KB Output is correct
19 Correct 31 ms 50760 KB Output is correct
20 Correct 33 ms 50712 KB Output is correct
21 Correct 27 ms 50512 KB Output is correct
22 Correct 27 ms 50760 KB Output is correct
23 Correct 27 ms 50760 KB Output is correct
24 Correct 18 ms 50760 KB Output is correct
25 Correct 18 ms 50768 KB Output is correct
26 Correct 20 ms 50760 KB Output is correct
27 Correct 29 ms 50768 KB Output is correct
28 Correct 28 ms 50948 KB Output is correct
29 Correct 32 ms 50700 KB Output is correct
30 Correct 33 ms 50624 KB Output is correct
31 Correct 27 ms 50768 KB Output is correct
32 Correct 26 ms 50780 KB Output is correct
33 Correct 36 ms 50768 KB Output is correct
34 Correct 31 ms 50768 KB Output is correct
35 Correct 34 ms 53036 KB Output is correct
36 Correct 26 ms 51016 KB Output is correct
37 Correct 38 ms 54532 KB Output is correct
38 Correct 34 ms 54344 KB Output is correct
39 Correct 34 ms 54352 KB Output is correct
40 Correct 33 ms 54352 KB Output is correct
41 Correct 33 ms 54344 KB Output is correct
42 Correct 26 ms 51272 KB Output is correct
43 Correct 30 ms 51408 KB Output is correct
44 Correct 30 ms 51456 KB Output is correct
45 Correct 130 ms 58184 KB Output is correct
46 Correct 94 ms 58184 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 50504 KB Output is correct
2 Correct 19 ms 50512 KB Output is correct
3 Correct 22 ms 50564 KB Output is correct
4 Correct 25 ms 50520 KB Output is correct
5 Correct 24 ms 50504 KB Output is correct
6 Correct 26 ms 50524 KB Output is correct
7 Correct 29 ms 50504 KB Output is correct
8 Correct 24 ms 50588 KB Output is correct
9 Correct 23 ms 50512 KB Output is correct
10 Correct 22 ms 50680 KB Output is correct
11 Correct 22 ms 50736 KB Output is correct
12 Correct 24 ms 50512 KB Output is correct
13 Correct 30 ms 50504 KB Output is correct
14 Correct 25 ms 50768 KB Output is correct
15 Correct 25 ms 50720 KB Output is correct
16 Correct 22 ms 50596 KB Output is correct
17 Correct 25 ms 50768 KB Output is correct
18 Correct 22 ms 50624 KB Output is correct
19 Correct 20 ms 50768 KB Output is correct
20 Correct 20 ms 50760 KB Output is correct
21 Correct 28 ms 50768 KB Output is correct
22 Correct 22 ms 50768 KB Output is correct
23 Correct 24 ms 50792 KB Output is correct
24 Correct 22 ms 50768 KB Output is correct
25 Correct 25 ms 50760 KB Output is correct
26 Correct 22 ms 50760 KB Output is correct
27 Correct 20 ms 50756 KB Output is correct
28 Correct 23 ms 50908 KB Output is correct
29 Correct 26 ms 50748 KB Output is correct
30 Correct 22 ms 50660 KB Output is correct
31 Correct 25 ms 50544 KB Output is correct
32 Correct 26 ms 50768 KB Output is correct
33 Correct 34 ms 50768 KB Output is correct
34 Correct 29 ms 50768 KB Output is correct
35 Correct 29 ms 53072 KB Output is correct
36 Correct 21 ms 51024 KB Output is correct
37 Correct 32 ms 54608 KB Output is correct
38 Correct 31 ms 54352 KB Output is correct
39 Correct 29 ms 54332 KB Output is correct
40 Correct 34 ms 54244 KB Output is correct
41 Correct 37 ms 54344 KB Output is correct
42 Correct 26 ms 51280 KB Output is correct
43 Correct 17 ms 51280 KB Output is correct
44 Correct 22 ms 51280 KB Output is correct
45 Correct 128 ms 58184 KB Output is correct
46 Correct 110 ms 58084 KB Output is correct
47 Correct 84 ms 70468 KB Output is correct
48 Correct 44 ms 56392 KB Output is correct
49 Correct 40 ms 55376 KB Output is correct
50 Correct 35 ms 54560 KB Output is correct
51 Correct 58 ms 59932 KB Output is correct
52 Correct 60 ms 59988 KB Output is correct
53 Correct 32 ms 51784 KB Output is correct
54 Correct 26 ms 50504 KB Output is correct
55 Correct 26 ms 50512 KB Output is correct
56 Correct 39 ms 52824 KB Output is correct
57 Correct 29 ms 50768 KB Output is correct
58 Correct 36 ms 51288 KB Output is correct
59 Correct 35 ms 51272 KB Output is correct
60 Correct 33 ms 52304 KB Output is correct
61 Correct 37 ms 52296 KB Output is correct
62 Correct 68 ms 63020 KB Output is correct
63 Execution timed out 1087 ms 193636 KB Time limit exceeded
64 Halted 0 ms 0 KB -