Submission #31825

#	Time	Username	Problem	Language	Result	Execution time	Memory
31825		minchurl	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	100 / 100	853 ms	4880 KiB

skyscraper

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#define MAX_N 30005
#define inf 0x3fffffff
using namespace std;
struct emp{
	int b,p,i;
	vector<int> list;
	int next,prev;
	bool operator < (emp d) const{
		if(b==d.b)	return p<d.p;
		return b<d.b;
	}
} arr[MAX_N];
int N,M,S,E;
int hn,heap[MAX_N],hloc[MAX_N],dst[MAX_N],chk[MAX_N],num[MAX_N];
bool hchk[MAX_N];
void upheap(int x){
	int y;
	while(x>1){
		y=x/2;
		if(dst[heap[x]]>=dst[heap[y]])	return;
		swap(heap[x],heap[y]);
		hloc[heap[x]]=x;
		hloc[heap[y]]=y;
		x=y;
	}
}
void downheap(int x){
	int y;
	while(2*x<=hn){
		y=2*x;
		if(y<hn && dst[heap[y+1]]<=dst[heap[y]])	y++;
		if(dst[heap[x]]<=dst[heap[y]])	return;
		swap(heap[x],heap[y]);
		hloc[heap[x]]=x;
		hloc[heap[y]]=y;
		x=y;
	}
}
int remove(){
	int x;
	x=heap[1];
	heap[1]=heap[hn];
	hloc[heap[1]]=1;
	hn--;
	downheap(1);
	hchk[x]=false;
	if(arr[x].prev!=-1)	arr[arr[x].prev].next=arr[x].next;
	arr[arr[x].next].prev=arr[x].prev;
	return x;
}
int dijkstra(){
	int i,j,x,y,z,maxx=0,sz;
	for(i=0;i<N;i++)	dst[i]=inf;
	dst[S]=0;
	heap[++hn]=S;
	hloc[S]=hn;
	hchk[S]=true;
	while(hn){
		x=remove();
		if(x==E)	break;
		sz=arr[x].list.size();
		for(i=0;i<sz;i++){
			for(j=arr[x].b+arr[x].list[i];j<M;j+=arr[x].list[i]){
				y=num[j];
				if(!y)	continue;
				y--;
				z=dst[x]+(abs(arr[x].b-arr[y].b))/arr[x].list[i];
				if(dst[y]>z){
					dst[y]=dst[x]+(abs(arr[x].b-arr[y].b))/arr[x].list[i];
					if(hchk[y]==false){
						heap[++hn]=y;
						hloc[y]=hn;
						hchk[y]=true;
					}
					upheap(hloc[y]);
				}else if(arr[y].list[0]==arr[x].list[i])	break;
			}
			for(j=arr[x].b-arr[x].list[i];j>=0;j-=arr[x].list[i]){
				y=num[j];
				if(!y)	continue;
				y--;
				z=dst[x]+(abs(arr[x].b-arr[y].b))/arr[x].list[i];
				if(dst[y]>z){
					dst[y]=dst[x]+(abs(arr[x].b-arr[y].b))/arr[x].list[i];
					if(hchk[y]==false){
						heap[++hn]=y;
						hloc[y]=hn;
						hchk[y]=true;
					}
					upheap(hloc[y]);
				}else if(arr[y].list[0]==arr[x].list[i])	break;
			}
		}
	}
	if(dst[E]==inf)	return -1;
	return dst[E];
}
int main(){
	int i,x;
	scanf("%d %d",&M,&N);
	for(i=0;i<N;i++){
		scanf("%d %d",&arr[i].b,&arr[i].p);
		arr[i].i=i;
	}
	sort(arr,arr+N);
	x=0;
	arr[x].prev=x-1;
	arr[x].next=x+1;
	arr[x].list.push_back(arr[0].p);
	arr[x++].b=arr[0].b;
	num[arr[0].b]=x;
	for(i=1;i<N;i++){
		if(arr[x-1].b!=arr[i].b){
			arr[x].prev=x-1;
			arr[x].next=x+1;
			arr[x++].b=arr[i].b;
			num[arr[i].b]=x;
		}
		arr[x-1].list.push_back(arr[i].p);
		if(arr[i].i==0)	S=x-1;
		if(arr[i].i==1)	E=x-1;
	}
	N=x;
	printf("%d\n",dijkstra());
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int dijkstra()':
skyscraper.cpp:56:16: warning: unused variable 'maxx' [-Wunused-variable]
  int i,j,x,y,z,maxx=0,sz;
                ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:104:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&M,&N);
                      ^
skyscraper.cpp:106:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&arr[i].b,&arr[i].p);
                                     ^

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