Submission #17333

#	Time	Username	Problem	Language	Result	Execution time	Memory
17333		comet	Jakarta Skyscrapers (APIO15_skyscraper)	C++98	57 / 100	1000 ms	4796 KiB

skyscraper

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> pp;
typedef vector<int> vec;
typedef vector<vec> mat;
#define pb push_back


int N,M;
int a[30010],P[30010];
int dist[30010];
bool chk[30010];

priority_queue<pp,vector<pp>,greater<pp> > Q;

mat doge;


int main(){
	scanf("%d%d",&N,&M);
	doge.assign(N,vec());
	for(int i=0;i<M;i++){
		scanf("%d%d",&a[i],&P[i]);
		doge[a[i]].push_back(P[i]);
	}

	memset(dist,0x3f,sizeof(dist));
	int INF=dist[0];
	dist[a[0]]=0;
	Q.push(pp(0,a[0]));

	int v;
	while(!Q.empty()){
		do{
			v=Q.top().second;Q.pop();
		}while(!Q.empty()&&chk[v]);
		chk[v]=1;
		if(v==a[1])break;
		for(int k=0;k<doge[v].size();k++){
			int p=doge[v][k];
			for(int i=v+p;i<N;i+=p){
				if(abs(v-i)%p==0){
					if(dist[i]>dist[v]+abs(v-i)/p){
						dist[i]=dist[v]+abs(v-i)/p;
						Q.push(pp(dist[i],i));
					}
				}
			}
			for(int i=v-p;i>=0;i-=p){
				if(abs(v-i)%p==0){
					if(dist[i]>dist[v]+abs(v-i)/p){
						dist[i]=dist[v]+abs(v-i)/p;
						Q.push(pp(dist[i],i));
					}
				}
			}
		}
	}

	if(dist[a[1]]==INF){
		puts("-1");
	}else{
		printf("%d",dist[a[1]]);
	}
}

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