Submission #17331

#	Time	Username	Problem	Language	Result	Execution time	Memory
17331		comet	Jakarta Skyscrapers (APIO15_skyscraper)	C++98	36 / 100	1000 ms	2364 KiB

skyscraper

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> pp;

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

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

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

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

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

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

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