oj.uz

Submission #494260

# Submission time Handle Problem Language Result Execution time Memory
494260 2021-12-14T22:28:40 Z aryan12 Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 1 ms 332 KB 
#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<pair<int, int> > doge(m + 1);
	vector<int> positions[n + 1];
	for(int i = 1; i <= m; i++) {
		cin >> doge[i].first >> doge[i].second; //position, jump;
		positions[doge[i].first].push_back(i);
	}
	vector<bool> vis(m + 1);
	vector<int> dist(m + 1);
	for(int i = 1; i <= m; i++) {
		vis[i] = false;
		dist[i] = INF;
	}
	dist[1] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
	pq.push({dist[1], 1});
	while(!pq.empty()) {
		int cur_dist = pq.top().first, cur_doge = pq.top().second;
		pq.pop();
		if(vis[cur_doge]) {
			continue;
		}
		if(cur_doge == 2) {
			break;
		}
		vis[cur_doge] = true;
		int cur_skyscraper = doge[cur_doge].first, cur_jump = doge[cur_doge].second;
		int new_dist = 1;
		for(int i = cur_skyscraper + cur_jump; i <= n; i += cur_jump) {
			for(int j = 0; j < positions[i].size(); j++) {
				if(vis[positions[i][j]]) {
					continue;
				}
				dist[positions[i][j]] = min(dist[positions[i][j]], cur_dist + new_dist);
				pq.push({cur_dist + new_dist, positions[i][j]});
			}
			new_dist++;
		}
		new_dist = 1;
		for(int i = cur_skyscraper - cur_jump; i > 0; i -= cur_jump) {
			for(int j = 0; j < positions[i].size(); j++) {
				if(vis[positions[i][j]]) {
					continue;
				}
				dist[positions[i][j]] = min(dist[positions[i][j]], cur_dist + new_dist);
				pq.push({cur_dist + new_dist, positions[i][j]});
			}
			new_dist++;
		}
	}
	if(dist[2] == INF) {
		cout << "-1\n";
		return;
	}
	cout << dist[2] << "\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

skyscraper.cpp: In function 'void Solve()':
skyscraper.cpp:40:21: 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]
   40 |    for(int j = 0; j < positions[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:51:21: 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]
   51 |    for(int j = 0; j < positions[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 208 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Incorrect 1 ms 208 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB Output isn't correct
3 Halted 0 ms 0 KB -