Submission #981424

#	Time	Username	Problem	Language	Result	Execution time	Memory
981424		Faisal_Saqib	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	442 ms	7372 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
const int NP=3e4+10;
const int NP1=3e4+10;
const long long inf=1e18;
long long dist[NP1];
int b[NP],p[NP];
vector<int> len[NP1];
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int j=0;j<n;j++)
		dist[j]=inf;
	for(int j=0;j<m;j++)
	{
		cin>>b[j]>>p[j];
		len[b[j]].push_back(p[j]);
	}
	priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> dp;
	dp.push({0,b[0]});
	dist[b[0]]=0;
	while(dp.size())
	{
		auto f=(dp.top());
        dp.pop();
		if(f.second==b[1])
		{
			cout<<f.first<<'\n';
			break;
		}
		for(auto lp:len[f.second])
		{
			int po=f.second+lp;
			int le=1;
			while(po<n)
			{
				if(dist[po]>f.first+le)
				{
					dist[po]=f.first+le;
					dp.push({dist[po],po});
				}
				po+=lp;
				le++;
			}
			po=f.second-lp;
			le=1;
			while(po>=0)
			{
				if(dist[po]>f.first+le)
				{
					dist[po]=f.first+le;
					dp.push({dist[po],po});
				}
				po-=lp;
				le++;
			}
		}
	}
	if(dist[b[1]]==inf)
		cout<<-1<<'\n';
	return 0;
}

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