Submission #17356

#	Time	Username	Problem	Language	Result	Execution time	Memory
17356		comet	Jakarta Skyscrapers (APIO15_skyscraper)	C++98	100 / 100	110 ms	10908 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
#define B 170

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

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]);
		if(P[i]<B){
			chk[a[i]][P[i]]=1;
		}
	}

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

	int v,d;
	while(!Q.empty()){
		v=Q.top().second;d=Q.top().first;Q.pop();
		if(dist[v]!=d)continue;
		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(dist[i]>dist[v]+(i-v)/p){
					dist[i]=dist[v]+(i-v)/p;
					Q.push(pp(dist[i],i));
				}
				if(p<B&&chk[i][p])break;
				if(p<B)chk[i][p]=1;
			}
			for(int i=v-p;i>=0;i-=p){
				if(dist[i]>dist[v]+(v-i)/p){
					dist[i]=dist[v]+(v-i)/p;
					Q.push(pp(dist[i],i));
				}
				if(p<B&&chk[i][p])break;
				if(p<B)chk[i][p]=1;
			}
		}
	}
	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: 43 / 43