Submission #261029

#	Time	Username	Problem	Language	Result	Execution time	Memory
261029		user202729	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1084 ms	4348 KiB

skyscraper

// 4
// ...
#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 EdgeCluster{int first, lastInclusive, power;};
	std::vector<std::vector<EdgeCluster>> 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; next>=0; next-=power){
			if(std::binary_search(begin(lengthsAt[next]), end(lengthsAt[next]), power) or next-power<0){
				add[home].push_back({next, home-power, power});
				break;
			}
		}
		for(int next=home+power; next<numBlock; next+=power){
			if(std::binary_search(begin(lengthsAt[next]), end(lengthsAt[next]), power) or next+power>=numBlock){
				add[home].push_back({home+power, 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 [first, lastInclusive, power]: add[node]){
			if(first==node+power){
				for(int next=first, length=1; next<=lastInclusive; next+=power,++length){
					auto nextDistance=curDistance+length;
					if(nextDistance<distance[next]){
						queue.push({next, distance[next]=nextDistance});
					}
				}
			}else{
				assert(lastInclusive==node-power);
				for(int next=lastInclusive, length=1; next>=first; next-=power,++length){
					auto nextDistance=curDistance+length;
					if(nextDistance<distance[next]){
						queue.push({next, distance[next]=nextDistance});
					}
				}
			}
		}
	}
	std::cout<<"-1\n";
}

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