# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
27266 | 2017-07-12T05:23:46 Z | TAMREF | Jakarta Skyscrapers (APIO15_skyscraper) | C++11 | 189 ms | 262144 KB |
#include <bits/stdc++.h> #define va first #define vb second #define mp make_pair using namespace std; typedef pair<int,int> pii; const int mx=30005; int B[mx], P[mx], dist[mx]; int N,M; vector<pii> G[mx]; void input(){ scanf("%d%d",&N,&M); for(int i=0;i<M;i++){ scanf("%d%d",&B[i],&P[i]); for(int s=B[i]+P[i];s<N;s+=P[i]) G[B[i]].push_back(mp((s-B[i])/P[i],s)); for(int s=B[i]-P[i];s>=0;s-=P[i]) G[B[i]].push_back(mp((B[i]-s)/P[i],s)); } fill(dist,dist+N,(int)1e9); } void dijk(int s){ priority_queue<pii,vector<pii>,greater<pii>> q; q.push(mp(dist[s]=0,s)); pii t; while(!q.empty()){ t=q.top(); q.pop(); //printf("now : %d, %d vs %d\n",t.vb,t.va,dist[t.vb]); if(t.va>dist[t.vb]) continue; //printf("%d\n",t.vb); for(pii z : G[t.vb]){ if(dist[z.vb]>dist[t.vb]+z.va){ q.push(mp(dist[z.vb]=dist[t.vb]+z.va,z.vb)); } } } } int main(){ input(); dijk(B[0]); printf("%d\n",dist[B[1]]==(int)1e9?-1:dist[B[1]]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3072 KB | Output is correct |
2 | Correct | 0 ms | 3072 KB | Output is correct |
3 | Correct | 0 ms | 3072 KB | Output is correct |
4 | Correct | 0 ms | 3072 KB | Output is correct |
5 | Correct | 0 ms | 3072 KB | Output is correct |
6 | Correct | 0 ms | 3072 KB | Output is correct |
7 | Correct | 0 ms | 3072 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3072 KB | Output is correct |
2 | Correct | 0 ms | 3072 KB | Output is correct |
3 | Correct | 0 ms | 3072 KB | Output is correct |
4 | Correct | 0 ms | 3072 KB | Output is correct |
5 | Correct | 0 ms | 3072 KB | Output is correct |
6 | Correct | 0 ms | 3072 KB | Output is correct |
7 | Correct | 0 ms | 3072 KB | Output is correct |
8 | Correct | 0 ms | 3072 KB | Output is correct |
9 | Correct | 0 ms | 3072 KB | Output is correct |
10 | Correct | 0 ms | 3072 KB | Output is correct |
11 | Correct | 0 ms | 3204 KB | Output is correct |
12 | Correct | 0 ms | 6232 KB | Output is correct |
13 | Correct | 0 ms | 6236 KB | Output is correct |
14 | Correct | 0 ms | 3204 KB | Output is correct |
15 | Correct | 0 ms | 3204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3072 KB | Output is correct |
2 | Correct | 0 ms | 3072 KB | Output is correct |
3 | Correct | 0 ms | 3072 KB | Output is correct |
4 | Correct | 0 ms | 3072 KB | Output is correct |
5 | Correct | 0 ms | 3072 KB | Output is correct |
6 | Correct | 0 ms | 3072 KB | Output is correct |
7 | Correct | 0 ms | 3072 KB | Output is correct |
8 | Correct | 0 ms | 3072 KB | Output is correct |
9 | Correct | 0 ms | 3072 KB | Output is correct |
10 | Correct | 0 ms | 3072 KB | Output is correct |
11 | Correct | 0 ms | 3204 KB | Output is correct |
12 | Correct | 6 ms | 6232 KB | Output is correct |
13 | Correct | 3 ms | 6236 KB | Output is correct |
14 | Correct | 0 ms | 3204 KB | Output is correct |
15 | Correct | 0 ms | 3204 KB | Output is correct |
16 | Correct | 0 ms | 3204 KB | Output is correct |
17 | Correct | 0 ms | 3336 KB | Output is correct |
18 | Correct | 0 ms | 3204 KB | Output is correct |
19 | Correct | 0 ms | 3204 KB | Output is correct |
20 | Correct | 49 ms | 35100 KB | Output is correct |
21 | Correct | 0 ms | 3072 KB | Output is correct |
22 | Correct | 0 ms | 3208 KB | Output is correct |
23 | Correct | 0 ms | 3204 KB | Output is correct |
24 | Correct | 0 ms | 3204 KB | Output is correct |
25 | Correct | 0 ms | 3212 KB | Output is correct |
26 | Correct | 53 ms | 52436 KB | Output is correct |
27 | Correct | 49 ms | 52364 KB | Output is correct |
28 | Correct | 0 ms | 3336 KB | Output is correct |
29 | Correct | 3 ms | 4068 KB | Output is correct |
30 | Correct | 0 ms | 3512 KB | Output is correct |
31 | Correct | 3 ms | 3636 KB | Output is correct |
32 | Correct | 0 ms | 3516 KB | Output is correct |
33 | Correct | 6 ms | 4720 KB | Output is correct |
34 | Correct | 3 ms | 4744 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3072 KB | Output is correct |
2 | Correct | 0 ms | 3072 KB | Output is correct |
3 | Correct | 0 ms | 3072 KB | Output is correct |
4 | Correct | 0 ms | 3072 KB | Output is correct |
5 | Correct | 0 ms | 3072 KB | Output is correct |
6 | Correct | 0 ms | 3072 KB | Output is correct |
7 | Correct | 0 ms | 3072 KB | Output is correct |
8 | Correct | 0 ms | 3072 KB | Output is correct |
9 | Correct | 0 ms | 3072 KB | Output is correct |
10 | Correct | 0 ms | 3072 KB | Output is correct |
11 | Correct | 0 ms | 3204 KB | Output is correct |
12 | Correct | 3 ms | 6232 KB | Output is correct |
13 | Correct | 3 ms | 6236 KB | Output is correct |
14 | Correct | 0 ms | 3204 KB | Output is correct |
15 | Correct | 0 ms | 3204 KB | Output is correct |
16 | Correct | 0 ms | 3204 KB | Output is correct |
17 | Correct | 0 ms | 3336 KB | Output is correct |
18 | Correct | 0 ms | 3204 KB | Output is correct |
19 | Correct | 0 ms | 3204 KB | Output is correct |
20 | Correct | 53 ms | 35100 KB | Output is correct |
21 | Correct | 0 ms | 3072 KB | Output is correct |
22 | Correct | 0 ms | 3208 KB | Output is correct |
23 | Correct | 0 ms | 3204 KB | Output is correct |
24 | Correct | 0 ms | 3204 KB | Output is correct |
25 | Correct | 0 ms | 3212 KB | Output is correct |
26 | Correct | 56 ms | 52436 KB | Output is correct |
27 | Correct | 46 ms | 52364 KB | Output is correct |
28 | Correct | 0 ms | 3336 KB | Output is correct |
29 | Correct | 3 ms | 4068 KB | Output is correct |
30 | Correct | 0 ms | 3512 KB | Output is correct |
31 | Correct | 3 ms | 3636 KB | Output is correct |
32 | Correct | 0 ms | 3516 KB | Output is correct |
33 | Correct | 6 ms | 4720 KB | Output is correct |
34 | Correct | 3 ms | 4744 KB | Output is correct |
35 | Correct | 9 ms | 4664 KB | Output is correct |
36 | Correct | 3 ms | 3340 KB | Output is correct |
37 | Correct | 13 ms | 6404 KB | Output is correct |
38 | Correct | 19 ms | 5852 KB | Output is correct |
39 | Correct | 19 ms | 6068 KB | Output is correct |
40 | Correct | 16 ms | 5892 KB | Output is correct |
41 | Correct | 13 ms | 5796 KB | Output is correct |
42 | Memory limit exceeded | 189 ms | 262144 KB | Memory limit exceeded |
43 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3072 KB | Output is correct |
2 | Correct | 0 ms | 3072 KB | Output is correct |
3 | Correct | 0 ms | 3072 KB | Output is correct |
4 | Correct | 0 ms | 3072 KB | Output is correct |
5 | Correct | 0 ms | 3072 KB | Output is correct |
6 | Correct | 0 ms | 3072 KB | Output is correct |
7 | Correct | 0 ms | 3072 KB | Output is correct |
8 | Correct | 0 ms | 3072 KB | Output is correct |
9 | Correct | 0 ms | 3072 KB | Output is correct |
10 | Correct | 0 ms | 3072 KB | Output is correct |
11 | Correct | 0 ms | 3204 KB | Output is correct |
12 | Correct | 0 ms | 6232 KB | Output is correct |
13 | Correct | 0 ms | 6236 KB | Output is correct |
14 | Correct | 0 ms | 3204 KB | Output is correct |
15 | Correct | 0 ms | 3204 KB | Output is correct |
16 | Correct | 0 ms | 3204 KB | Output is correct |
17 | Correct | 0 ms | 3336 KB | Output is correct |
18 | Correct | 0 ms | 3204 KB | Output is correct |
19 | Correct | 0 ms | 3204 KB | Output is correct |
20 | Correct | 53 ms | 35100 KB | Output is correct |
21 | Correct | 0 ms | 3072 KB | Output is correct |
22 | Correct | 0 ms | 3208 KB | Output is correct |
23 | Correct | 0 ms | 3204 KB | Output is correct |
24 | Correct | 0 ms | 3204 KB | Output is correct |
25 | Correct | 0 ms | 3212 KB | Output is correct |
26 | Correct | 39 ms | 52436 KB | Output is correct |
27 | Correct | 46 ms | 52364 KB | Output is correct |
28 | Correct | 0 ms | 3336 KB | Output is correct |
29 | Correct | 3 ms | 4068 KB | Output is correct |
30 | Correct | 0 ms | 3512 KB | Output is correct |
31 | Correct | 3 ms | 3636 KB | Output is correct |
32 | Correct | 0 ms | 3516 KB | Output is correct |
33 | Correct | 3 ms | 4720 KB | Output is correct |
34 | Correct | 6 ms | 4744 KB | Output is correct |
35 | Correct | 9 ms | 4664 KB | Output is correct |
36 | Correct | 3 ms | 3340 KB | Output is correct |
37 | Correct | 13 ms | 6404 KB | Output is correct |
38 | Correct | 16 ms | 5852 KB | Output is correct |
39 | Correct | 16 ms | 6068 KB | Output is correct |
40 | Correct | 13 ms | 5892 KB | Output is correct |
41 | Correct | 9 ms | 5796 KB | Output is correct |
42 | Memory limit exceeded | 169 ms | 262144 KB | Memory limit exceeded |
43 | Halted | 0 ms | 0 KB | - |