Submission #197309

#	Time	Username	Problem	Language	Result	Execution time	Memory
197309		Juney	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	265 ms	72148 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e4 + 5;

int N, M, B[MAXN], D[MAXN], S, E;
vector<int> V[MAXN];
vector<pii> G[MAXN];

void solve() {
	for(int i=0; i<N; i++) D[i] = 1e9;
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	D[S] = 0;
	pq.push(pii(0, S));
	while(!pq.empty()) {
		int cur = pq.top().se, dis = pq.top().fi; pq.pop();
		if(D[cur] < dis) continue;
		for(auto nxt : G[cur]) if(dis + nxt.se < D[nxt.fi]) {
			D[nxt.fi] = dis + nxt.se;
			pq.push(pii(D[nxt.fi], nxt.fi));
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M;
	for(int i=0; i<M; i++) {
		int b, p;
		cin >> b >> p;
		V[p].push_back(b);
		if(i == 0) S = b;
		if(i == 1) E = b;
	}
	for(int i=1; i<=30000; i++) {
		for(int j : V[i]) B[j] = i;
		sort(V[i].begin(), V[i].end());
		V[i].erase(unique(V[i].begin(), V[i].end()), V[i].end());
		for(int j=0; j<V[i].size(); j++) {
			for(int b=V[i][j]+i, dis=1; b<N; b+=i, dis++) {
				G[V[i][j]].push_back(pii(b, dis));
				if(B[b] == i) break;
			}
			for(int b=V[i][j]-i, dis=1; b>=0; b-=i, dis++) {
				G[V[i][j]].push_back(pii(b, dis));
				if(B[b] == i) break;
			}
		}
	}
	solve();
	if(D[E] == (int)1e9) cout << -1;
	else cout << D[E];
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<V[i].size(); j++) {
                ~^~~~~~~~~~~~

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