Submission #31812

#	Time	Username	Problem	Language	Result	Execution time	Memory
31812		minchurl	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	57 / 100	1000 ms	4500 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;
	int next,prev;
	vector<int> list;
	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];
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,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++){
			y=arr[x].prev;
			while(y!=-1){
				if((arr[x].b-arr[y].b)%arr[x].list[i]){y=arr[y].prev;continue;}
				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]);
				}
				y=arr[y].prev;
			}
			y=arr[x].next;
			while(y<N){
				if((arr[x].b-arr[y].b)%arr[x].list[i]){y=arr[y].next;continue;}
				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]);
				}
				y=arr[y].next;
			}
		}
	}
	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;
	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;
		}
		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:14: warning: unused variable 'maxx' [-Wunused-variable]
  int i,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: 0 / 43