제출 #882728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
882728		Onur_Ilgaz	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	580 ms	7632 KiB

skyscraper

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;

int32_t main(){
	fast
	int n, m;
	cin >> n >> m;
	vector<vector<int> > guy(n);
	int st = -1, to = -1;
	for(int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		if(st == -1) st = a;
		else if(to == -1) to = a;
		guy[a].push_back(b);
	}
	priority_queue <pair<int, int> > pq;
	vector <int> dis(n, inf);
	dis[st] = 0;
	pq.push({0, st});
	bitset <200000> calc;
	while(!pq.empty()) {
		int val = -pq.top().first, node = pq.top().second;
		// cout << node << ": \n";
		pq.pop();
		if(calc[node]) continue;
		calc[node] = 1;
		for(auto mult:guy[node]) {
			// cout << mult << ",\n";
			int give = 1;
			for(int i = node + mult; i < n; i+=mult, give++) {
				if(val + give < dis[i]) {
					dis[i] = val + give;
					pq.push({-dis[i],i});
					// cout << i << "\n";
				}
			}
			give = 1;
			for(int i = node - mult; i >= 0; i-=mult, give++) {
				if(val + give < dis[i]) {
					dis[i] = val + give;
					pq.push({-dis[i],i});
					// cout << i << "\n";
				}
			}
		}
	}
	if(dis[to] > 1e8) cout << -1 << "\n";
	else cout << dis[to] << "\n";
}

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