# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
27346 | 2017-07-12T10:16:49 Z | TAMREF | Jakarta Skyscrapers (APIO15_skyscraper) | C++11 | 1000 ms | 4524 KB |
#include <bits/stdc++.h> #define va first #define vb second #define mp make_pair #define all(x) x.begin(),x.end() using namespace std; typedef pair<int,int> pii; const int mx=30005; int dist[mx]; pii doge[mx]; vector<int> C[mx]; int N,M; void input(){ scanf("%d%d",&N,&M); for(int i=0;i<M;i++){ scanf("%d%d",&doge[i].va,&doge[i].vb); C[doge[i].va].push_back(doge[i].vb); } for(int i=0;i<N;i++) sort(all(C[i]),greater<int>()); 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; int vis[mx]; while(!q.empty()){ t=q.top(); q.pop(); if(t.va>dist[t.vb]) continue; for(int i=0;i<N;i++) vis[i]=0; for(int p : C[t.vb]){ for(int x=t.vb+p;x<N;x+=p){ if(!C[x].size()||vis[x]) continue; vis[x]=1; if(binary_search(all(C[x]),p)){ if(dist[x]>=t.va+(x-t.vb)/p){ q.push(mp(dist[x]=t.va+(x-t.vb)/p,x)); break; } } if(dist[x]>=t.va+(x-t.vb)/p) q.push(mp(dist[x]=t.va+(x-t.vb)/p,x)); } for(int x=t.vb-p;x>=0;x-=p){ if(!C[x].size()||vis[x]) continue; vis[x]=1; if(binary_search(all(C[x]),p)){ if(dist[x]>=t.va+(t.vb-x)/p){ q.push(mp(dist[x]=t.va+(t.vb-x)/p,x)); break; } } if(dist[x]>=t.va+(t.vb-x)/p) q.push(mp(dist[x]=t.va+(t.vb-x)/p,x)); } } } } int main(){ input(); dijk(doge[0].va); printf("%d\n",dist[doge[1].va]==(int)1e9?-1:dist[doge[1].va]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3076 KB | Output is correct |
2 | Correct | 0 ms | 3076 KB | Output is correct |
3 | Correct | 0 ms | 3076 KB | Output is correct |
4 | Correct | 0 ms | 3076 KB | Output is correct |
5 | Correct | 0 ms | 3076 KB | Output is correct |
6 | Correct | 0 ms | 3076 KB | Output is correct |
7 | Correct | 0 ms | 3076 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3076 KB | Output is correct |
2 | Correct | 0 ms | 3076 KB | Output is correct |
3 | Correct | 0 ms | 3076 KB | Output is correct |
4 | Correct | 0 ms | 3076 KB | Output is correct |
5 | Correct | 0 ms | 3076 KB | Output is correct |
6 | Correct | 0 ms | 3076 KB | Output is correct |
7 | Correct | 0 ms | 3076 KB | Output is correct |
8 | Correct | 0 ms | 3076 KB | Output is correct |
9 | Correct | 0 ms | 3076 KB | Output is correct |
10 | Correct | 0 ms | 3076 KB | Output is correct |
11 | Correct | 0 ms | 3076 KB | Output is correct |
12 | Correct | 0 ms | 3076 KB | Output is correct |
13 | Correct | 0 ms | 3076 KB | Output is correct |
14 | Correct | 0 ms | 3076 KB | Output is correct |
15 | Correct | 0 ms | 3076 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3076 KB | Output is correct |
2 | Correct | 0 ms | 3076 KB | Output is correct |
3 | Correct | 0 ms | 3076 KB | Output is correct |
4 | Correct | 0 ms | 3076 KB | Output is correct |
5 | Correct | 0 ms | 3076 KB | Output is correct |
6 | Correct | 0 ms | 3076 KB | Output is correct |
7 | Correct | 0 ms | 3076 KB | Output is correct |
8 | Correct | 0 ms | 3076 KB | Output is correct |
9 | Correct | 0 ms | 3076 KB | Output is correct |
10 | Correct | 0 ms | 3076 KB | Output is correct |
11 | Correct | 0 ms | 3076 KB | Output is correct |
12 | Correct | 0 ms | 3076 KB | Output is correct |
13 | Correct | 0 ms | 3076 KB | Output is correct |
14 | Correct | 0 ms | 3076 KB | Output is correct |
15 | Correct | 0 ms | 3076 KB | Output is correct |
16 | Correct | 0 ms | 3076 KB | Output is correct |
17 | Correct | 3 ms | 3208 KB | Output is correct |
18 | Correct | 0 ms | 3076 KB | Output is correct |
19 | Correct | 0 ms | 3076 KB | Output is correct |
20 | Correct | 16 ms | 3208 KB | Output is correct |
21 | Correct | 0 ms | 3076 KB | Output is correct |
22 | Correct | 0 ms | 3076 KB | Output is correct |
23 | Correct | 0 ms | 3076 KB | Output is correct |
24 | Correct | 3 ms | 3220 KB | Output is correct |
25 | Correct | 3 ms | 3208 KB | Output is correct |
26 | Correct | 6 ms | 3076 KB | Output is correct |
27 | Correct | 6 ms | 3076 KB | Output is correct |
28 | Correct | 3 ms | 3208 KB | Output is correct |
29 | Correct | 0 ms | 3076 KB | Output is correct |
30 | Correct | 0 ms | 3076 KB | Output is correct |
31 | Correct | 0 ms | 3076 KB | Output is correct |
32 | Correct | 0 ms | 3076 KB | Output is correct |
33 | Correct | 0 ms | 3076 KB | Output is correct |
34 | Correct | 0 ms | 3076 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3076 KB | Output is correct |
2 | Correct | 0 ms | 3076 KB | Output is correct |
3 | Correct | 0 ms | 3076 KB | Output is correct |
4 | Correct | 0 ms | 3076 KB | Output is correct |
5 | Correct | 0 ms | 3076 KB | Output is correct |
6 | Correct | 0 ms | 3076 KB | Output is correct |
7 | Correct | 0 ms | 3076 KB | Output is correct |
8 | Correct | 0 ms | 3076 KB | Output is correct |
9 | Correct | 0 ms | 3076 KB | Output is correct |
10 | Correct | 0 ms | 3076 KB | Output is correct |
11 | Correct | 0 ms | 3076 KB | Output is correct |
12 | Correct | 0 ms | 3076 KB | Output is correct |
13 | Correct | 0 ms | 3076 KB | Output is correct |
14 | Correct | 0 ms | 3076 KB | Output is correct |
15 | Correct | 0 ms | 3076 KB | Output is correct |
16 | Correct | 0 ms | 3076 KB | Output is correct |
17 | Correct | 3 ms | 3208 KB | Output is correct |
18 | Correct | 0 ms | 3076 KB | Output is correct |
19 | Correct | 0 ms | 3076 KB | Output is correct |
20 | Correct | 19 ms | 3208 KB | Output is correct |
21 | Correct | 0 ms | 3076 KB | Output is correct |
22 | Correct | 0 ms | 3076 KB | Output is correct |
23 | Correct | 0 ms | 3076 KB | Output is correct |
24 | Correct | 3 ms | 3220 KB | Output is correct |
25 | Correct | 3 ms | 3208 KB | Output is correct |
26 | Correct | 9 ms | 3076 KB | Output is correct |
27 | Correct | 6 ms | 3076 KB | Output is correct |
28 | Correct | 3 ms | 3208 KB | Output is correct |
29 | Correct | 0 ms | 3076 KB | Output is correct |
30 | Correct | 0 ms | 3076 KB | Output is correct |
31 | Correct | 0 ms | 3076 KB | Output is correct |
32 | Correct | 0 ms | 3076 KB | Output is correct |
33 | Correct | 0 ms | 3076 KB | Output is correct |
34 | Correct | 0 ms | 3076 KB | Output is correct |
35 | Correct | 23 ms | 3480 KB | Output is correct |
36 | Correct | 3 ms | 3208 KB | Output is correct |
37 | Correct | 43 ms | 3476 KB | Output is correct |
38 | Correct | 33 ms | 3524 KB | Output is correct |
39 | Correct | 43 ms | 3520 KB | Output is correct |
40 | Correct | 43 ms | 3524 KB | Output is correct |
41 | Correct | 43 ms | 3524 KB | Output is correct |
42 | Correct | 123 ms | 3352 KB | Output is correct |
43 | Correct | 149 ms | 3352 KB | Output is correct |
44 | Correct | 119 ms | 3348 KB | Output is correct |
45 | Correct | 9 ms | 3208 KB | Output is correct |
46 | Correct | 9 ms | 3340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3076 KB | Output is correct |
2 | Correct | 0 ms | 3076 KB | Output is correct |
3 | Correct | 0 ms | 3076 KB | Output is correct |
4 | Correct | 0 ms | 3076 KB | Output is correct |
5 | Correct | 0 ms | 3076 KB | Output is correct |
6 | Correct | 0 ms | 3076 KB | Output is correct |
7 | Correct | 0 ms | 3076 KB | Output is correct |
8 | Correct | 0 ms | 3076 KB | Output is correct |
9 | Correct | 0 ms | 3076 KB | Output is correct |
10 | Correct | 0 ms | 3076 KB | Output is correct |
11 | Correct | 0 ms | 3076 KB | Output is correct |
12 | Correct | 0 ms | 3076 KB | Output is correct |
13 | Correct | 0 ms | 3076 KB | Output is correct |
14 | Correct | 0 ms | 3076 KB | Output is correct |
15 | Correct | 0 ms | 3076 KB | Output is correct |
16 | Correct | 0 ms | 3076 KB | Output is correct |
17 | Correct | 3 ms | 3208 KB | Output is correct |
18 | Correct | 0 ms | 3076 KB | Output is correct |
19 | Correct | 0 ms | 3076 KB | Output is correct |
20 | Correct | 16 ms | 3208 KB | Output is correct |
21 | Correct | 0 ms | 3076 KB | Output is correct |
22 | Correct | 0 ms | 3076 KB | Output is correct |
23 | Correct | 0 ms | 3076 KB | Output is correct |
24 | Correct | 3 ms | 3220 KB | Output is correct |
25 | Correct | 3 ms | 3208 KB | Output is correct |
26 | Correct | 6 ms | 3076 KB | Output is correct |
27 | Correct | 6 ms | 3076 KB | Output is correct |
28 | Correct | 3 ms | 3208 KB | Output is correct |
29 | Correct | 0 ms | 3076 KB | Output is correct |
30 | Correct | 0 ms | 3076 KB | Output is correct |
31 | Correct | 0 ms | 3076 KB | Output is correct |
32 | Correct | 0 ms | 3076 KB | Output is correct |
33 | Correct | 0 ms | 3076 KB | Output is correct |
34 | Correct | 0 ms | 3076 KB | Output is correct |
35 | Correct | 19 ms | 3480 KB | Output is correct |
36 | Correct | 3 ms | 3208 KB | Output is correct |
37 | Correct | 43 ms | 3476 KB | Output is correct |
38 | Correct | 36 ms | 3524 KB | Output is correct |
39 | Correct | 43 ms | 3520 KB | Output is correct |
40 | Correct | 36 ms | 3524 KB | Output is correct |
41 | Correct | 36 ms | 3524 KB | Output is correct |
42 | Correct | 123 ms | 3352 KB | Output is correct |
43 | Correct | 113 ms | 3352 KB | Output is correct |
44 | Correct | 116 ms | 3348 KB | Output is correct |
45 | Correct | 9 ms | 3208 KB | Output is correct |
46 | Correct | 9 ms | 3340 KB | Output is correct |
47 | Correct | 266 ms | 4272 KB | Output is correct |
48 | Correct | 6 ms | 3604 KB | Output is correct |
49 | Correct | 6 ms | 3604 KB | Output is correct |
50 | Correct | 6 ms | 3472 KB | Output is correct |
51 | Correct | 413 ms | 4520 KB | Output is correct |
52 | Correct | 456 ms | 4524 KB | Output is correct |
53 | Correct | 303 ms | 4136 KB | Output is correct |
54 | Correct | 0 ms | 3076 KB | Output is correct |
55 | Correct | 0 ms | 3076 KB | Output is correct |
56 | Execution timed out | 1000 ms | 4000 KB | Execution timed out |
57 | Halted | 0 ms | 0 KB | - |