Submission #204548

#	Time	Username	Problem	Language	Result	Execution time	Memory
204548		cgiosy	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	5 ms	384 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);cin.tie(nullptr);
	int N, M, st=0, ed=0;
	cin>>N>>M;
	vector<vector<int>> A(N);
	for(int i=0; i<N; 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) A[x].push_back(m);
	}
	for(auto&v:A) {
		sort(rbegin(v), rend(v));
		v.erase(unique(begin(v), end(v)), end(v));
	}

	vector<int> D(N, INT_MAX);
	vector<vector<int>> Q(N);
	int qs=1, k=0, n=0;
	Q[0].push_back(st); D[st]=0;
	while(qs) {
		for(int x:Q[k]) if(D[x]==n) {
			if(x==ed) { cout<<n; return 0; }
			for(int m:A[x]) {
				for(int i=x+m, j=k+1, d=D[x]+1; i<N; i+=m, j=j+1-(j+1==N)*N, d++) {
					if(d<D[i]) D[i]=d, Q[j].push_back(i), qs++;
					if(binary_search(rbegin(A[i]), rend(A[i]), m)) break;
				}
				for(int i=x-m, j=k+1, d=D[x]+1; i>=0; i-=m, j=j+1-(j+1==N)*N, d++) {
					if(d<D[i]) D[i]=d, Q[j].push_back(i), qs++;
					if(binary_search(rbegin(A[i]), rend(A[i]), m)) break;
				}
			}
		}
		qs-=Q[k].size();
		Q[k].clear();
		k=k+1-(k+1==N)*N;
		++n;
	}
	cout<<-1;
}

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