Submission #1288097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288097		lambd47	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	36 / 100	1098 ms	32628 KiB

skyscraper

#include<bits/stdc++.h>

using namespace std;

#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())





void solve(){
	int n,m;
	cin>>n>>m;
	vector<vector<pair<int,int>>> adj(m);
	vector<int> pos(m);
	vector<int> pulo(m);
	L(i,0,m-1)cin>>pos[i]>>pulo[i];
	
	
	auto dist=[&](int i, int j)->int{
		if(abs(pos[i]-pos[j])%pulo[i])return -1;
		return abs(pos[i]-pos[j])/pulo[i];
	};
	L(i,0,m-1){
		L(j,0,m-1){
			if(i==j)continue;
			if(dist(i,j)==-1)continue;
			adj[i].push_back({j,dist(i,j)});
		}
	}
	const int MOD=1e9+7;
	vector<int> dp(m,MOD);
	dp[0]=0;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	pq.push({dp[0],0});
	while(!pq.empty()){
		auto [d,v]=pq.top();
		pq.pop();
		if(d!=dp[v])continue;
		for(auto [node,w]:adj[v]){
			if(dp[node]>dp[v]+w){
				dp[node]=dp[v]+w;
				pq.push({dp[node],node});
			}
		}
	}	
	cout<<((dp[1]==MOD)?-1:dp[1]);
	
	
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	solve();
}
//fazer um pseudo floyd warshal, na vdd da pra construir um super clique com as distancias de cada u

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