Submission #488587

#	Time	Username	Problem	Language	Result	Execution time	Memory
488587		pooyashams	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	425 ms	169268 KiB

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 = 55;
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 = 50;
	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 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43