oj.uz

Submission #519455

# Submission time Handle Problem Language Result Execution time Memory
519455 2022-01-26T11:50:34 Z Drew_ Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 3 ms 2252 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second
 
#define fastio ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(x) cerr << "[" << #x << "]: " << x << "\n";
 
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using pl = pair<ll, ll>;
 
constexpr ld PI = 4*atan((ld)1);
constexpr int MAX = 30069;
constexpr int SQ = 10;	
constexpr int inf = 1e9 + 69;
 
int n, m;
int cost[MAX][SQ];
 
int b[MAX], p[MAX];
vector<int> adj[MAX];	
 
int main()
{
	fastio;
 
	for (int i = 0; i < MAX; ++i)
		for (int j = 0; j < SQ; ++j)
			cost[i][j] = inf;
 
	cin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		cin >> b[i] >> p[i];
		if (i) adj[b[i]].pb(p[i]);
	}
 
	const auto valid = [&](int pos) -> bool
	{
		return 0 <= pos && pos < n;
	};
 
	priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;
	
	cost[b[0]][0] = 0;
	if (p[0] < SQ)
	{
		cost[b[0]][p[0]] = 0;
		pq.push({0, p[0], b[0]});
	}
	else
	{
		for (int i = b[0], ctr = 0; i >= 0; i -= p[0], ++ctr)
		{
			if (cost[i][0] > ctr)
				cost[i][0] = ctr, pq.push({ctr, 0, i});
		}
		for (int i = b[0], ctr = 0; i < n; i += p[0], ++ctr)
		{
			if (cost[i][0] > ctr)
				cost[i][0] = ctr, pq.push({ctr, 0, i});
		}
	}
 
	
	while (!pq.empty())
	{
		auto [c, mov, pos] = pq.top();
		pq.pop();
 
		if (cost[pos][mov] < c)
			continue;
 
		if (mov)
		{		
			if (valid(pos - mov) && cost[pos - mov][mov] > 1 + c)
			{
				cost[pos - mov][0] = min(cost[pos - mov][0], 1 + c);
				cost[pos - mov][mov] = 1 + c;
				pq.push({1 + c, mov, pos - mov});
			}
			if (valid(pos + mov) && cost[pos + mov][mov] > 1 + c)
			{
				cost[pos + mov][0] = min(cost[pos + mov][0], 1 + c);
				cost[pos + mov][mov] = 1 + c;
				pq.push({1 + c, mov, pos + mov});
			}
		}
 
 
		for (int x : adj[pos])
		{
			if (x < SQ)
			{
				if (valid(pos - x) && cost[pos - x][x] > 1 + c)
				{
					cost[pos - x][0] = min(cost[pos - x][0], 1 + c);
					cost[pos - x][x] = 1 + c;
					pq.push({1 + c, x, pos - x});
				}
				if (valid(pos + x) && cost[pos + x][x] > 1 + c)
				{
					cost[pos + x][0] = min(cost[pos + x][0], 1 + c);
					cost[pos + x][x] = 1 + c;
					pq.push({1 + c, x, pos + x});
				}
			}
			else
			{
				for (int i = pos, ctr = c; i >= 0; i -= x, ++ctr)
				{
					if (cost[i][0] > ctr)
						cost[i][0] = ctr, pq.push({ctr, 0, i});
				}
				for (int i = pos, ctr = c; i < n; i += x, ++ctr)
				{
					if (cost[i][0] > ctr)
						cost[i][0] = ctr, pq.push({ctr, 0, i});
				}
			}
		}
		adj[pos].clear();
	}
 	 
	cout << (cost[b[1]][0] == inf ? -1 : cost[b[1]][0]) << '\n';
 
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2124 KB Output is correct
2 Correct 2 ms 2200 KB Output is correct
3 Correct 1 ms 2124 KB Output is correct
4 Correct 2 ms 2124 KB Output is correct
5 Correct 2 ms 2124 KB Output is correct
6 Correct 1 ms 2124 KB Output is correct
7 Correct 2 ms 2124 KB Output is correct
8 Correct 1 ms 2124 KB Output is correct
9 Correct 1 ms 2124 KB Output is correct
10 Correct 2 ms 2124 KB Output is correct
11 Incorrect 3 ms 2252 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2192 KB Output is correct
2 Correct 2 ms 2124 KB Output is correct
3 Correct 2 ms 2124 KB Output is correct
4 Correct 1 ms 2124 KB Output is correct
5 Correct 2 ms 2196 KB Output is correct
6 Correct 2 ms 2124 KB Output is correct
7 Correct 1 ms 2124 KB Output is correct
8 Correct 1 ms 2124 KB Output is correct
9 Correct 2 ms 2124 KB Output is correct
10 Correct 2 ms 2196 KB Output is correct
11 Incorrect 2 ms 2252 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2124 KB Output is correct
2 Correct 2 ms 2204 KB Output is correct
3 Correct 2 ms 2196 KB Output is correct
4 Correct 1 ms 2124 KB Output is correct
5 Correct 2 ms 2200 KB Output is correct
6 Correct 2 ms 2200 KB Output is correct
7 Correct 1 ms 2124 KB Output is correct
8 Correct 2 ms 2124 KB Output is correct
9 Correct 1 ms 2128 KB Output is correct
10 Correct 2 ms 2200 KB Output is correct
11 Incorrect 2 ms 2252 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2124 KB Output is correct
2 Correct 1 ms 2124 KB Output is correct
3 Correct 2 ms 2124 KB Output is correct
4 Correct 1 ms 2196 KB Output is correct
5 Correct 2 ms 2124 KB Output is correct
6 Correct 1 ms 2124 KB Output is correct
7 Correct 1 ms 2196 KB Output is correct
8 Correct 2 ms 2124 KB Output is correct
9 Correct 2 ms 2124 KB Output is correct
10 Correct 2 ms 2124 KB Output is correct
11 Incorrect 2 ms 2252 KB Output isn't correct
12 Halted 0 ms 0 KB -