제출 #905584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
905584		Muhammad_Aneeq	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	1062 ms	2716 KiB

skyscraper

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <set>
#include <queue>
using namespace std;
int const M=35000;
int dp[M]={};
void solve()
{
	int n,m;
	cin>>n>>m;
	pair<int,int>a[m];
	for (auto& i:a)
		cin>>i.first>>i.second;
	for (int i=0;i<m;i++)
		dp[i]=1e9+10;
	dp[0]=0;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>s;
	s.push({0,0});
	int vis[m]={};
	set<int>f;
	for (int i=1;i<m;i++)
		f.insert(i);
	while (s.size())
	{
		int i=s.top().second;
		s.pop();
		if (vis[i])
			continue;
		vis[i]=0;
		f.erase(i);
		for (auto j:f)
		{
			if (abs(a[i].first-a[j].first)%a[i].second==0&&dp[j]>dp[i]+abs(a[i].first-a[j].first)/a[i].second)
			{
					dp[j]=dp[i]+abs(a[i].first-a[j].first)/a[i].second;
					s.push({dp[j],j});
			}
		}
	}
	cout<<(dp[1]==1e9+10?-1:dp[1])<<endl;
}
signed main()
{
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
        solve();
}

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