Submission #1237880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237880		djsksbrbf	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	176 ms	67640 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
#define pb push_back
#define fi first
#define se second
const int MAX = 3e5 + 5;
const int MOD = 1e9 + 7;
#define int ll

int n,m;

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
//	vector <pii> v(m);
//	for(auto &it : v)cin >> it.fi >> it.se;
//	for(int i = 0 ; i < m ; i++){
//		for(int j = 0 ; j < m ; j++){
//			if(i== j)continue;
//			ll dis = abs(v[i].fi - v[j].fi);
//			if(dis % v[i].se)continue;
//			
//			adj[i].pb({j, dis / v[i].se});
//		}
//	}
//	
//	ll dist[m + 4];
//	bool vis[m];memset(vis, 0, sizeof(vis));
//	for(int i = 0 ; i <= m ; i++)dist[i] = (ll)1e18;
//	dist[0] = 0;
//	for(int i = 0 ; i < m ; i++){
//		int t = -1;
//		for(int j = 0 ; j < m ; j++){
//			if(!vis[j] && (t == -1 || dist[j] < dist[t])){
//				t = j;
//			}
//		}
//		
//		if(dist[t] == (ll)1e18){
//			cout << -1 << endl;
//			return 0;
//		}
//		if(t == 1){
//			cout << dist[t] << endl;
//			return 0;
//		}
//		
//		vis[t] = 1;
//		for(auto [nxt, we] : adj[t]){
//			if(dist[nxt] > dist[t] + we){
//				dist[nxt] = dist[t] + we;
//			}
//		}
//	}
//	cout << -1 << endl;
	
	
	int st, en;
	vector <set<int>> bs(n);
	vector <pii> adj[n];
	
	for(int i = 0 ; i < m ; i++){
		int b, p; cin >> b >> p;
		bs[b].insert(p);
		
		if(i == 0)st = b;
		if(i == 1)en = b;
	}
	
	for(int u = 0 ; u < n ; u++){
		for(auto doge : bs[u]){
			for(int v = u - doge ; v >= 0 ; v -= doge){
				adj[u].pb({v, (u - v) / doge});
				if(bs[v].find(doge) != bs[v].end())break;
			}
			
			for(int  v = u + doge ; v < n ; v += doge){
				adj[u].pb({v, (v - u) / doge});
				if(bs[v].find(doge) != bs[v].end())break;
			}
		}
	}
	
	priority_queue <pii, vector <pii>, greater<pii>> pq;
	ll vis[n];
	for(int i = 0 ; i < n ; i++)vis[i] = MOD;
	pq.push({0, st});
	
	while(pq.size()){
		auto [dist, u] = pq.top(); pq.pop();
		if(u == en){
			cout << dist << endl;
			return 0;
		}
		
		for(auto[v, w] : adj[u]){
			if(dist + w < vis[v]){
				vis[v] = dist + w;
				pq.push({vis[v], v});
			}
		}
	}
	cout << -1 << endl;
	
	return 0;
}

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