# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
31824 | 2017-09-10T15:21:09 Z | minchurl | Jakarta Skyscrapers (APIO15_skyscraper) | C++11 | 1000 ms | 4644 KB |
#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; 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; 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]); } } 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]); } } } } 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].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++].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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3720 KB | Output is correct |
2 | Correct | 0 ms | 3720 KB | Output is correct |
3 | Correct | 0 ms | 3720 KB | Output is correct |
4 | Correct | 0 ms | 3720 KB | Output is correct |
5 | Correct | 0 ms | 3720 KB | Output is correct |
6 | Correct | 0 ms | 3720 KB | Output is correct |
7 | Correct | 0 ms | 3720 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3720 KB | Output is correct |
2 | Correct | 0 ms | 3720 KB | Output is correct |
3 | Correct | 0 ms | 3720 KB | Output is correct |
4 | Correct | 0 ms | 3720 KB | Output is correct |
5 | Correct | 0 ms | 3720 KB | Output is correct |
6 | Correct | 0 ms | 3720 KB | Output is correct |
7 | Correct | 0 ms | 3720 KB | Output is correct |
8 | Correct | 0 ms | 3720 KB | Output is correct |
9 | Correct | 0 ms | 3720 KB | Output is correct |
10 | Correct | 0 ms | 3720 KB | Output is correct |
11 | Correct | 0 ms | 3720 KB | Output is correct |
12 | Correct | 0 ms | 3720 KB | Output is correct |
13 | Correct | 0 ms | 3720 KB | Output is correct |
14 | Correct | 0 ms | 3720 KB | Output is correct |
15 | Correct | 0 ms | 3720 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3720 KB | Output is correct |
2 | Correct | 0 ms | 3720 KB | Output is correct |
3 | Correct | 0 ms | 3720 KB | Output is correct |
4 | Correct | 0 ms | 3720 KB | Output is correct |
5 | Correct | 0 ms | 3720 KB | Output is correct |
6 | Correct | 0 ms | 3720 KB | Output is correct |
7 | Correct | 0 ms | 3720 KB | Output is correct |
8 | Correct | 0 ms | 3720 KB | Output is correct |
9 | Correct | 0 ms | 3720 KB | Output is correct |
10 | Correct | 0 ms | 3720 KB | Output is correct |
11 | Correct | 0 ms | 3720 KB | Output is correct |
12 | Correct | 0 ms | 3720 KB | Output is correct |
13 | Correct | 3 ms | 3720 KB | Output is correct |
14 | Correct | 0 ms | 3720 KB | Output is correct |
15 | Correct | 0 ms | 3720 KB | Output is correct |
16 | Correct | 0 ms | 3720 KB | Output is correct |
17 | Correct | 0 ms | 3720 KB | Output is correct |
18 | Correct | 0 ms | 3720 KB | Output is correct |
19 | Correct | 0 ms | 3720 KB | Output is correct |
20 | Correct | 33 ms | 3852 KB | Output is correct |
21 | Correct | 0 ms | 3720 KB | Output is correct |
22 | Correct | 0 ms | 3720 KB | Output is correct |
23 | Correct | 0 ms | 3720 KB | Output is correct |
24 | Correct | 0 ms | 3720 KB | Output is correct |
25 | Correct | 0 ms | 3720 KB | Output is correct |
26 | Correct | 0 ms | 3720 KB | Output is correct |
27 | Correct | 0 ms | 3720 KB | Output is correct |
28 | Correct | 3 ms | 3852 KB | Output is correct |
29 | Correct | 0 ms | 3720 KB | Output is correct |
30 | Correct | 0 ms | 3720 KB | Output is correct |
31 | Correct | 0 ms | 3720 KB | Output is correct |
32 | Correct | 0 ms | 3720 KB | Output is correct |
33 | Correct | 0 ms | 3720 KB | Output is correct |
34 | Correct | 0 ms | 3720 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3720 KB | Output is correct |
2 | Correct | 0 ms | 3720 KB | Output is correct |
3 | Correct | 0 ms | 3720 KB | Output is correct |
4 | Correct | 0 ms | 3720 KB | Output is correct |
5 | Correct | 0 ms | 3720 KB | Output is correct |
6 | Correct | 0 ms | 3720 KB | Output is correct |
7 | Correct | 0 ms | 3720 KB | Output is correct |
8 | Correct | 0 ms | 3720 KB | Output is correct |
9 | Correct | 0 ms | 3720 KB | Output is correct |
10 | Correct | 0 ms | 3720 KB | Output is correct |
11 | Correct | 0 ms | 3720 KB | Output is correct |
12 | Correct | 0 ms | 3720 KB | Output is correct |
13 | Correct | 3 ms | 3720 KB | Output is correct |
14 | Correct | 0 ms | 3720 KB | Output is correct |
15 | Correct | 0 ms | 3720 KB | Output is correct |
16 | Correct | 0 ms | 3720 KB | Output is correct |
17 | Correct | 0 ms | 3720 KB | Output is correct |
18 | Correct | 0 ms | 3720 KB | Output is correct |
19 | Correct | 0 ms | 3720 KB | Output is correct |
20 | Correct | 23 ms | 3852 KB | Output is correct |
21 | Correct | 0 ms | 3720 KB | Output is correct |
22 | Correct | 0 ms | 3720 KB | Output is correct |
23 | Correct | 0 ms | 3720 KB | Output is correct |
24 | Correct | 3 ms | 3720 KB | Output is correct |
25 | Correct | 0 ms | 3720 KB | Output is correct |
26 | Correct | 0 ms | 3720 KB | Output is correct |
27 | Correct | 0 ms | 3720 KB | Output is correct |
28 | Correct | 0 ms | 3852 KB | Output is correct |
29 | Correct | 0 ms | 3720 KB | Output is correct |
30 | Correct | 0 ms | 3720 KB | Output is correct |
31 | Correct | 0 ms | 3720 KB | Output is correct |
32 | Correct | 0 ms | 3720 KB | Output is correct |
33 | Correct | 0 ms | 3720 KB | Output is correct |
34 | Correct | 0 ms | 3720 KB | Output is correct |
35 | Correct | 13 ms | 3852 KB | Output is correct |
36 | Correct | 3 ms | 3720 KB | Output is correct |
37 | Correct | 6 ms | 3852 KB | Output is correct |
38 | Correct | 13 ms | 3984 KB | Output is correct |
39 | Correct | 16 ms | 3984 KB | Output is correct |
40 | Correct | 13 ms | 3984 KB | Output is correct |
41 | Correct | 9 ms | 3984 KB | Output is correct |
42 | Correct | 9 ms | 3996 KB | Output is correct |
43 | Correct | 3 ms | 3992 KB | Output is correct |
44 | Correct | 356 ms | 3988 KB | Output is correct |
45 | Correct | 13 ms | 3852 KB | Output is correct |
46 | Correct | 9 ms | 3852 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3720 KB | Output is correct |
2 | Correct | 0 ms | 3720 KB | Output is correct |
3 | Correct | 0 ms | 3720 KB | Output is correct |
4 | Correct | 0 ms | 3720 KB | Output is correct |
5 | Correct | 0 ms | 3720 KB | Output is correct |
6 | Correct | 0 ms | 3720 KB | Output is correct |
7 | Correct | 0 ms | 3720 KB | Output is correct |
8 | Correct | 0 ms | 3720 KB | Output is correct |
9 | Correct | 0 ms | 3720 KB | Output is correct |
10 | Correct | 0 ms | 3720 KB | Output is correct |
11 | Correct | 0 ms | 3720 KB | Output is correct |
12 | Correct | 0 ms | 3720 KB | Output is correct |
13 | Correct | 0 ms | 3720 KB | Output is correct |
14 | Correct | 0 ms | 3720 KB | Output is correct |
15 | Correct | 0 ms | 3720 KB | Output is correct |
16 | Correct | 0 ms | 3720 KB | Output is correct |
17 | Correct | 0 ms | 3720 KB | Output is correct |
18 | Correct | 0 ms | 3720 KB | Output is correct |
19 | Correct | 0 ms | 3720 KB | Output is correct |
20 | Correct | 23 ms | 3852 KB | Output is correct |
21 | Correct | 0 ms | 3720 KB | Output is correct |
22 | Correct | 0 ms | 3720 KB | Output is correct |
23 | Correct | 0 ms | 3720 KB | Output is correct |
24 | Correct | 0 ms | 3720 KB | Output is correct |
25 | Correct | 0 ms | 3720 KB | Output is correct |
26 | Correct | 0 ms | 3720 KB | Output is correct |
27 | Correct | 0 ms | 3720 KB | Output is correct |
28 | Correct | 0 ms | 3852 KB | Output is correct |
29 | Correct | 0 ms | 3720 KB | Output is correct |
30 | Correct | 0 ms | 3720 KB | Output is correct |
31 | Correct | 0 ms | 3720 KB | Output is correct |
32 | Correct | 0 ms | 3720 KB | Output is correct |
33 | Correct | 0 ms | 3720 KB | Output is correct |
34 | Correct | 0 ms | 3720 KB | Output is correct |
35 | Correct | 13 ms | 3852 KB | Output is correct |
36 | Correct | 3 ms | 3720 KB | Output is correct |
37 | Correct | 9 ms | 3852 KB | Output is correct |
38 | Correct | 16 ms | 3984 KB | Output is correct |
39 | Correct | 13 ms | 3984 KB | Output is correct |
40 | Correct | 13 ms | 3984 KB | Output is correct |
41 | Correct | 13 ms | 3984 KB | Output is correct |
42 | Correct | 9 ms | 3996 KB | Output is correct |
43 | Correct | 6 ms | 3992 KB | Output is correct |
44 | Correct | 316 ms | 3988 KB | Output is correct |
45 | Correct | 13 ms | 3852 KB | Output is correct |
46 | Correct | 13 ms | 3852 KB | Output is correct |
47 | Correct | 13 ms | 4116 KB | Output is correct |
48 | Correct | 9 ms | 4248 KB | Output is correct |
49 | Correct | 6 ms | 4248 KB | Output is correct |
50 | Correct | 6 ms | 4116 KB | Output is correct |
51 | Correct | 16 ms | 4380 KB | Output is correct |
52 | Correct | 19 ms | 4380 KB | Output is correct |
53 | Correct | 16 ms | 4380 KB | Output is correct |
54 | Correct | 0 ms | 3720 KB | Output is correct |
55 | Correct | 0 ms | 3720 KB | Output is correct |
56 | Execution timed out | 1000 ms | 4644 KB | Execution timed out |
57 | Halted | 0 ms | 0 KB | - |