Submission #494267

#	Time	Username	Problem	Language	Result	Execution time	Memory
494267		aryan12	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	974 ms	3528 KiB

skyscraper

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

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e15;

void Solve() {
	int n, m;
	cin >> n >> m;
	vector<int> pos[n + 1];
	vector<pair<int, int> > doge(m + 1);
	for(int i = 1; i <= m; i++) {
		cin >> doge[i].first >> doge[i].second;
		doge[i].first++;
		pos[doge[i].first].push_back(i);
	}
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
	int dist[n + 1];
	for(int i = 0; i <= n; i++) {
		dist[i] = INF;
	}
	dist[doge[1].first] = 0;
	pq.push({dist[doge[1].first], doge[1].first});
	while(!pq.empty()) {
		int cur_dist = pq.top().first, cur_skyskraper = pq.top().second;
		pq.pop();
		if(cur_dist > dist[cur_skyskraper]) {
			continue;
		}
		for(int i = 0; i < pos[cur_skyskraper].size(); i++) {
			int jump = doge[pos[cur_skyskraper][i]].second, cnt = 1;
			for(int j = cur_skyskraper - jump; j > 0; j -= jump) {
				if(dist[j] > dist[cur_skyskraper] + cnt) {
					dist[j] = dist[cur_skyskraper] + cnt;
					if(pos[j].size() != 0) {
						pq.push({dist[j], j});
					}
				}
				cnt++;
			}
			cnt = 1;
			for(int j = cur_skyskraper + jump; j <= n; j += jump) {
				if(dist[j] > dist[cur_skyskraper] + cnt) {
					dist[j] = dist[cur_skyskraper] + cnt;
					if(pos[j].size() != 0) {
						pq.push({dist[j], j});
					}
				}
				cnt++;
			}
		}
	}
	if(dist[doge[2].first] == INF) {
		cout << "-1\n";
	}
	else {
		cout << dist[doge[2].first] << "\n";
	}
}

int32_t main() {
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void Solve()':
skyscraper.cpp:32:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int i = 0; i < pos[cur_skyskraper].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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