Submission #261021

#	Time	Username	Problem	Language	Result	Execution time	Memory
261021		user202729	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	416 ms	262148 KiB

skyscraper

// 4
// That shouldn't be able to pass subtask 1.
#ifndef LOCAL
#define NDEBUG 1
#endif
#include<bits/stdc++.h>

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	int numBlock, numDog; std::cin>>numBlock>>numDog;
	std::vector<std::vector<int>> lengthsAt(numBlock);
	struct T{int home, power;};
	std::vector<T> data(numDog);
	for(auto& [home, power]: data){
		std::cin>>home>>power;
		lengthsAt[home].push_back(power);
	}
	for(auto& it: lengthsAt){
		std::sort(begin(it), end(it));
		it.erase(std::unique(begin(it), end(it)), end(it));
	}

	struct Edge{int node, length;};
	std::vector<std::vector<Edge>> add(numBlock);
	/*
	auto const indexBlock=[&](int block){return block;};
	auto const indexDog=[&](int dog){return dog+numBlock;};
	*/

	for(int dog=0; dog<numDog; ++dog){
		auto [home, power]=data[dog];
		for(int next=home-power, length=1; next>=0; next-=power,++length){
			add[home].push_back({next, length});
			if(std::binary_search(begin(lengthsAt[next]), end(lengthsAt[next]), power)) break;
		}
		for(int next=home+power, length=1; next<numBlock; next+=power,++length){
			add[home].push_back({next, length});
			if(std::binary_search(begin(lengthsAt[next]), end(lengthsAt[next]), power)) break;
		}
	}

	struct State{int node, distance;
		bool operator<(State other) const{return distance>other.distance;}
	};
	std::vector<int> distance(add.size(), INT_MAX);
	std::priority_queue<State> queue;
	queue.push({data[0].home, distance[data[0].home]=0});

	while(not queue.empty()){
		auto [node, curDistance]=queue.top(); queue.pop();
		if(curDistance!=distance[node]) continue;
		if(node==data[1].home){
			std::cout<<curDistance<<'\n';
			return 0;
		}
		for(auto [other, edgeLength]: add[node]){
			auto nextDistance=curDistance+edgeLength;
			if(nextDistance<distance[other]){
				queue.push({other, distance[other]=nextDistance});
			}
		}
	}
	std::cout<<"-1\n";
}

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