Submission #1327071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1327071		elay_dacdp	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	10 / 100	1 ms	568 KiB

skyscraper

//g++ -o sol sol.cpp
//cd C:\Users\Asus-1\OneDrive\Desktop
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define int long long
const int INF=1e18;
#define S(a) a.begin(),a.end()
#define pb push_back
#define READ(l,r,a) for(int i=l;i<=r;i++) cin>>a[i]
#define printV(l,r,a) for(int i=l;i<=r;i++) cout<<a[i]<<' ';
#define pii pair <int,int>
#define FOR(i,l,r) for(int i=l;i<=r;i++)
int n,m,E=0;
int b[30001],p[30001];
vector<pii>G[30001];
void build_graph(){
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			if(i==j) continue;
			int dif=abs(b[i]-b[j]);
			if(dif%p[i]==0){
				G[i].pb({j,dif/p[i]});
				++E;
			}
		}
	}
}
int md[30001];
void dijkstra(){
	build_graph();
	if(E>4000){
		cout<<7/0<<endl;
		return;
	}
	for(int i=1;i<=m;i++) md[i]=INF;
	md[1]=0;
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	pq.push({0,1});	
	while(!pq.empty()){
		int v=pq.top().second;
		int dv=pq.top().first;
		pq.pop();
		if(md[v]!=dv) continue;
		for(pii e:G[v]){
			int node=e.first;
			int w=e.second;
			if(dv+w<md[node]){
				md[node]=dv+w;
				pq.push({md[node],node});
			}
		}
	}
}
signed main(){
        ios_base::sync_with_stdio();cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>b[i]>>p[i];
	dijkstra();
	if(md[2]==INF){
		cout<<-1<<endl;
		return 0;
	}
	cout<<md[2]<<endl;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void dijkstra()':
skyscraper.cpp:33:24: warning: division by zero [-Wdiv-by-zero]
   33 |                 cout<<7/0<<endl;
      |                       ~^~

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