제출 #204630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
204630		cgiosy	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	441 ms	114416 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
 
struct pii {
	int x, i;
	bool operator<(const pii b) const { return x>b.x; }
};
int main() {
	ios_base::sync_with_stdio(false);cin.tie(nullptr);
	int N, M, st=0, ed=-1;
	cin>>N>>M;
	vector<int> D(N, INT_MAX);
	vector<vector<int>> A(N);
	vector<bitset<30208>> V(N);
	for(int i=0; i<M; i++) {
		int x, m;
		cin>>x>>m;
		if(i==0) st=x;
		else if(i==1) ed=x;
		if(max(x, N-1-x)>=m && !V[x][m]) A[x].push_back(m), V[x][m]=true;
	}
 
	priority_queue<pii> q;
	q.push({0, st}); D[st]=0;
	while(q.size()) {
		auto[n,x]=q.top(); q.pop();
		if(D[x]!=n) continue;
		if(x==ed) { cout<<n; return 0; }
		for(int m:A[x]) {
			for(int i=x+m, d=n+1; i<N; i+=m, d++) if(d<D[i]) {
				D[i]=d, q.push({d, i});
				if(V[i][m]) break;
				V[i][m]=true;
			}
			for(int i=x-m, d=n+1; i>=0; i-=m, d++) if(d<D[i]) {
				D[i]=d, q.push({d, i});
				if(V[i][m]) break;
				V[i][m]=true;
			}
		}
	}
	cout<<-1;
}

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