Submission #488564

#	Time	Username	Problem	Language	Result	Execution time	Memory
488564		pooyashams	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	91 ms	197732 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;
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 = sqrt(n);
	for(int p = 0; 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(0);
	cout << dist[1] << endl;
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43