Submission #466710

#	Time	Username	Problem	Language	Result	Execution time	Memory
466710		ronnith	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	259 ms	80592 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

const int N = (int)3e4, M = (int)3e4;
int n, m;
array<int, 2> doge[M];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	set<int> P;
	vector<int> ind;
	for(int i = 0;i < m;i ++) {
		int b, p;
		cin >> b >> p;
		P.insert(p);
		doge[i] = {b, p};
	}
	for(auto& e: P) ind.push_back(e);
	auto id = [&](int x) {
		return lower_bound(ind.begin(), ind.end(), x) - ind.begin();
	};
	vector<set<int>> pos(n);
	for(int i = 0;i < m;i ++) {
		pos[doge[i][0]].insert(id(doge[i][1]));
	}
	vector<vector<pair<int, int>>> adj(n);
	set<array<int, 2>> same;
	for(int i = 0;i < m;i ++) {
		if(same.find(doge[i]) != same.end()) continue;
		same.insert(doge[i]);
		int it = doge[i][0]+doge[i][1];
		int cnt = 1;
		while(it < n) {
			adj[doge[i][0]].emplace_back(it, cnt);
			if(pos[it].find(id(doge[i][1])) != pos[it].end()) break;
			it += doge[i][1];
			cnt ++;
		}
		it = doge[i][0]-doge[i][1];
		cnt = 1;
		while(it >= 0) {
			adj[doge[i][0]].emplace_back(it, cnt);
			if(pos[it].find(id(doge[i][1])) != pos[it].end()) break;
			it -= doge[i][1];
			cnt ++;
		}
	}
	vector<int> dist(n, INT_MAX);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({0, doge[0][0]});
	dist[doge[0][0]] = 0;
	while((int)pq.size()) {
		auto X = pq.top();
		pq.pop();
		int d, x; tie(d, x) = X;
		if(d != dist[x]) continue;
		for(auto E : adj[x]) {
			int e, w;tie(e, w) = E;
			if(dist[e] > dist[x] + w) {
				dist[e] = dist[x] + w;
				pq.push({dist[e], e});
			}
		}
	}
	cout << (dist[doge[1][0]] == INT_MAX ? -1 : dist[doge[1][0]])  << '\n';
	return 0;
}

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