Submission #1168639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168639		tkm_algorithms	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	265 ms	327680 KiB

skyscraper

/**
*    In the name of Allah
*    We are nothing and you're everything
*    author: najmuddin
**/
#include <bits/stdc++.h>
using namespace std;
	
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
#define int ll
 
const char nl = '\n';
const int N = 1e5+5;
const int inf = 1e18+10;

void solve() {
	int n, m; cin >> n >> m;
	
	vector<int> b(m), p(m);
	vector<tuple<int, int>> g[n];
	set<pair<int, int>> st;
	for (int i = 0; i < m; ++i) {
		cin >> b[i] >> p[i];
		st.insert({b[i], p[i]});
	}
	
	for (auto i: st) {
		auto [x, y] = i;
		int k = 1;
		while (x-y*k >= 0)g[x].push_back({x-y*k, k}), k++;
		k = 1;
		while (x+y*k < n)g[x].push_back({x+y*k, k}), k++;
	}
	
	vector<int> vis(n+1, inf);
	vis[b[0]] = 0;
	
	queue<tuple<int, int>> q;
	q.push({b[0], 0});
	
	while (!q.empty()) {
		auto [x, a] = q.front();
		q.pop();
		
		for (auto [i, w]: g[x]) {
			if (vis[i] > w+a)q.push({i, a+w}), vis[i] = a+w;
		}
	}
	
	if (vis[b[1]] == inf)vis[b[1]] = -1;
	cout << vis[b[1]];
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    // freopen("input.txt", "r", stdin);
    
    int T = 1;
    for (int _ = 0; _ < T; ++_) {
		solve();
	}
	return 0;
}

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