제출 #679738

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679738		Iliya	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1095 ms	22772 KiB

skyscraper

//Ye Rooz Khoob Miad ???
#include<bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int) (x).size

using namespace std;
typedef long long ll;

const int N = 3e5 + 10;
const int Inf = 1'061'109'567;

unordered_set<int> In[N];
bool mark[N];
int n, m, B[N], P[N], D[N];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> B[i] >> P[i];
		In[B[i]].insert(P[i]);
	}
	priority_queue<pair<int, int>> PQ;
	memset(D, 63, sizeof D);
	D[B[0]] = 0;
	PQ.push({0, B[0]});
	while(!PQ.empty()) {
		int a = PQ.top().S;
		PQ.pop();
		if(mark[a]) continue;
		mark[a] = true;
		for(int x : In[a]) {
			for(int i = a; i < n; i += x) {
				if(D[i] > D[a] + (i - a) / x) {
					D[i] = D[a] + (i - a) / x;
					PQ.push({-D[i], i});
				}
			}
			for(int i = a; i >= 0; i -= x) {
				if(D[i] > D[a] + (a - i) / x) {
					D[i] = D[a] + (a - i) / x;
					PQ.push({-D[i], i});
				}
			}
		}
	}
	cout << (D[B[1]] == Inf ? -1 : D[B[1]]);

	return 0;
}

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