Submission #679733

#	Time	Username	Problem	Language	Result	Execution time	Memory
679733		faribourz	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	199 ms	70940 KiB

skyscraper

// Only GOD
// believe in yourself
// Nemidam Del Be In Darde Donya!
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define bit(x, y) ((x >> y)&1)
#define sz(x) (int)x.size()
#define kill(x) return cout << x << '\n', void()
#define KILL(x) return cout << x << '\n', 0
#define int ll

const int N = 1e5+100;
const int INF = 1e9+10;
set <int> s[N];
vector<pii> G[N];
int dis[N];
int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n, m;
	cin >> n >> m;
	int start = -1, end = -1;
	for(int i = 0; i < m; i++){
		int b, p;
		cin >> b >> p;
		s[b].insert(p);
		if(i==0)
			start = b;
		if(i==1)
			end = b;
	}
	memset(dis, 63, sizeof dis);
	for(int i = 0; i < n; i++){
		for(int u : s[i]){
			for(int j = i+u;j < n; j+= u){
				G[i].pb({j, (j-i)/u});
				if(s[j].find(u) != s[j].end()){
					break;
				}
			}
			for(int j = i - u; j >= 0; j-=u){
				G[i].pb({j, (i-j)/u});
				if(s[j].find(u) != s[j].end()){
					break;
				}
			}
		}
	}
	dis[start] = 0;
	priority_queue<pii> q;
	q.push({-dis[start], start});
	while(!q.empty()){
		int a = q.top().S;
		q.pop();
		for(auto B : G[a]){
			int v = B.F, w = B.S;
			if(dis[a] + w < dis[v]){
				dis[v] = dis[a]+w;
				q.push({-dis[v], v});
			}
		}
	}
	cout << (dis[end] > INF ? -1 : dis[end]);
}

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