Submission #679744

#	Time	Username	Problem	Language	Result	Execution time	Memory
679744		Iliya	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	86 ms	11868 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;
 
vector<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]].pb(P[i]);
	}
	map<pair<int, int>, bool> MP;
	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;
		In[a].resize(distance(In[a].begin(), unique(all(In[a]))));
		for(int x : In[a]) {
			pair<int, int> w = {a % x, x};
			if(MP[w]) continue;
			else MP[w] = true;
			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: 43 / 43