Submission #99463

#	Time	Username	Problem	Language	Result	Execution time	Memory
99463		Shafin666	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	379 ms	68744 KiB

skyscraper

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
typedef long double ld;
using namespace std;

vector<int> adj[30005], cost[30005];
set<int> s[30005]; 
int b[30005], dist[30005];

int main() 
{
	int n, m;
	int i, j, k;
	int x, y;

	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> x >> y; b[i] = x;
		s[x].insert(y);
	}

	for(int pos = 0; pos < n; pos++) {
		dist[pos] = 1e9+7;
		
		for(int p : s[pos]) {
			for(int i = 1; ; i++) {
				if(pos + i*p < n) {
					adj[pos].pb(pos + i*p);
					cost[pos].pb(i);

					if(s[pos + i*p].find(p) != s[pos + i*p].end()) break;
				} else break;
			}
			for(int i = 1; ; i++) {
				if(pos - i*p >= 0) {
					adj[pos].pb(pos - i*p);
					cost[pos].pb(i);

					if(s[pos - i*p].find(p) != s[pos - i*p].end()) break;
				} else break;
			}
		}
	}

	priority_queue<pii, vector<pii>, greater<pii>> pq;
	dist[b[0]] = 0; pq.push({dist[b[0]], b[0]});

	while(!pq.empty()) {
		pii p = pq.top();
		pq.pop();

		int u = p.second; int w = p.first;
		for(int i = 0; i < (int) adj[u].size(); i++) {
			int c = cost[u][i];
			int v = adj[u][i];

			if(dist[v] > w+c) {
				dist[v] = w+c;
				pq.push({dist[v], v});
			}
		}
	}
	if(dist[b[1]] >= 1e8) cout << -1 << endl;
	else cout << dist[b[1]] << endl; 

	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:16:6: warning: unused variable 'i' [-Wunused-variable]
  int i, j, k;
      ^
skyscraper.cpp:16:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k;
         ^
skyscraper.cpp:16:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^

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