# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
236173 | 2020-05-31T10:49:35 Z | thtsshz_bgwrswh | Jakarta Skyscrapers (APIO15_skyscraper) | C++17 | 336 ms | 262148 KB |
#pragma GCC optimize("Ofast") #include<stdio.h> #include<vector> #include<queue> #include<set> #include<utility> #include<algorithm> using namespace std; int pos[30005],power[30005],dis[30005]; vector<pair<int,int>> g[30005]; set<int> s[30005]; priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq; int main(){ int i,j,n,m; scanf("%d%d",&n,&m); for(i=0;i<m;i++){ scanf("%d%d",&pos[i],&power[i]); // if(i!=1) // s[pos[i]].insert(power[i]); } for(i=0;i<m;i++){ for(j=pos[i]+power[i];j<n;j+=power[i]){ g[pos[i]].emplace_back(j,(j-pos[i])/power[i]); if(s[j].count(power[i])) break; } for(j=pos[i]-power[i];j>=0;j-=power[i]){ g[pos[i]].emplace_back(j,(pos[i]-j)/power[i]); if(s[j].count(power[i])) break; } // break; } /*for(i=0;i<n;i++){ printf("%d\n",i); for(auto x:g[i]) printf("%d ",x.first); putchar('\n'); }*/ for(i=0;i<n;i++) dis[i]=1000000000; dis[pos[0]]=0; pq.push({0,pos[0]}); while(pq.size()){ auto v=pq.top().second; pq.pop(); for(auto x:g[v]){ if(dis[v]+x.second<dis[x.first]){ dis[x.first]=dis[v]+x.second; pq.push({dis[x.first],x.first}); } } } if(dis[pos[1]]==1000000000) puts("-1"); else printf("%d\n",dis[pos[1]]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2432 KB | Output is correct |
2 | Correct | 6 ms | 2432 KB | Output is correct |
3 | Correct | 6 ms | 2432 KB | Output is correct |
4 | Correct | 6 ms | 2432 KB | Output is correct |
5 | Correct | 6 ms | 2560 KB | Output is correct |
6 | Correct | 6 ms | 2432 KB | Output is correct |
7 | Correct | 6 ms | 2432 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2432 KB | Output is correct |
2 | Correct | 6 ms | 2432 KB | Output is correct |
3 | Correct | 7 ms | 2432 KB | Output is correct |
4 | Correct | 6 ms | 2432 KB | Output is correct |
5 | Correct | 6 ms | 2432 KB | Output is correct |
6 | Correct | 6 ms | 2432 KB | Output is correct |
7 | Correct | 6 ms | 2432 KB | Output is correct |
8 | Correct | 6 ms | 2432 KB | Output is correct |
9 | Correct | 6 ms | 2432 KB | Output is correct |
10 | Correct | 6 ms | 2432 KB | Output is correct |
11 | Correct | 6 ms | 2560 KB | Output is correct |
12 | Correct | 10 ms | 4724 KB | Output is correct |
13 | Correct | 11 ms | 4724 KB | Output is correct |
14 | Correct | 6 ms | 2560 KB | Output is correct |
15 | Correct | 6 ms | 2560 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2432 KB | Output is correct |
2 | Correct | 6 ms | 2432 KB | Output is correct |
3 | Correct | 6 ms | 2432 KB | Output is correct |
4 | Correct | 6 ms | 2432 KB | Output is correct |
5 | Correct | 7 ms | 2432 KB | Output is correct |
6 | Correct | 6 ms | 2432 KB | Output is correct |
7 | Correct | 6 ms | 2432 KB | Output is correct |
8 | Correct | 6 ms | 2432 KB | Output is correct |
9 | Correct | 6 ms | 2432 KB | Output is correct |
10 | Correct | 6 ms | 2432 KB | Output is correct |
11 | Correct | 6 ms | 2560 KB | Output is correct |
12 | Correct | 9 ms | 4596 KB | Output is correct |
13 | Correct | 9 ms | 4724 KB | Output is correct |
14 | Correct | 6 ms | 2560 KB | Output is correct |
15 | Correct | 6 ms | 2560 KB | Output is correct |
16 | Correct | 7 ms | 2560 KB | Output is correct |
17 | Correct | 7 ms | 2688 KB | Output is correct |
18 | Correct | 6 ms | 2560 KB | Output is correct |
19 | Correct | 6 ms | 2560 KB | Output is correct |
20 | Correct | 58 ms | 34552 KB | Output is correct |
21 | Correct | 6 ms | 2432 KB | Output is correct |
22 | Correct | 6 ms | 2560 KB | Output is correct |
23 | Correct | 7 ms | 2560 KB | Output is correct |
24 | Correct | 7 ms | 2688 KB | Output is correct |
25 | Correct | 7 ms | 2688 KB | Output is correct |
26 | Correct | 65 ms | 35532 KB | Output is correct |
27 | Correct | 62 ms | 35412 KB | Output is correct |
28 | Correct | 7 ms | 2688 KB | Output is correct |
29 | Correct | 8 ms | 3328 KB | Output is correct |
30 | Correct | 7 ms | 2816 KB | Output is correct |
31 | Correct | 7 ms | 2944 KB | Output is correct |
32 | Correct | 7 ms | 2816 KB | Output is correct |
33 | Correct | 10 ms | 3968 KB | Output is correct |
34 | Correct | 10 ms | 3968 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2432 KB | Output is correct |
2 | Correct | 6 ms | 2432 KB | Output is correct |
3 | Correct | 6 ms | 2432 KB | Output is correct |
4 | Correct | 6 ms | 2432 KB | Output is correct |
5 | Correct | 6 ms | 2432 KB | Output is correct |
6 | Correct | 6 ms | 2432 KB | Output is correct |
7 | Correct | 6 ms | 2432 KB | Output is correct |
8 | Correct | 6 ms | 2432 KB | Output is correct |
9 | Correct | 6 ms | 2432 KB | Output is correct |
10 | Correct | 6 ms | 2432 KB | Output is correct |
11 | Correct | 6 ms | 2560 KB | Output is correct |
12 | Correct | 9 ms | 4596 KB | Output is correct |
13 | Correct | 9 ms | 4724 KB | Output is correct |
14 | Correct | 6 ms | 2560 KB | Output is correct |
15 | Correct | 6 ms | 2484 KB | Output is correct |
16 | Correct | 7 ms | 2532 KB | Output is correct |
17 | Correct | 7 ms | 2688 KB | Output is correct |
18 | Correct | 6 ms | 2572 KB | Output is correct |
19 | Correct | 6 ms | 2560 KB | Output is correct |
20 | Correct | 60 ms | 34680 KB | Output is correct |
21 | Correct | 6 ms | 2432 KB | Output is correct |
22 | Correct | 6 ms | 2560 KB | Output is correct |
23 | Correct | 6 ms | 2560 KB | Output is correct |
24 | Correct | 7 ms | 2688 KB | Output is correct |
25 | Correct | 7 ms | 2560 KB | Output is correct |
26 | Correct | 64 ms | 35532 KB | Output is correct |
27 | Correct | 62 ms | 35540 KB | Output is correct |
28 | Correct | 7 ms | 2736 KB | Output is correct |
29 | Correct | 8 ms | 3456 KB | Output is correct |
30 | Correct | 7 ms | 2816 KB | Output is correct |
31 | Correct | 8 ms | 2944 KB | Output is correct |
32 | Correct | 7 ms | 2816 KB | Output is correct |
33 | Correct | 10 ms | 3968 KB | Output is correct |
34 | Correct | 10 ms | 3968 KB | Output is correct |
35 | Correct | 17 ms | 4480 KB | Output is correct |
36 | Correct | 8 ms | 2688 KB | Output is correct |
37 | Correct | 18 ms | 6016 KB | Output is correct |
38 | Correct | 20 ms | 5504 KB | Output is correct |
39 | Correct | 20 ms | 5760 KB | Output is correct |
40 | Correct | 20 ms | 5760 KB | Output is correct |
41 | Correct | 19 ms | 5504 KB | Output is correct |
42 | Runtime error | 321 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
43 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2432 KB | Output is correct |
2 | Correct | 6 ms | 2432 KB | Output is correct |
3 | Correct | 6 ms | 2432 KB | Output is correct |
4 | Correct | 6 ms | 2432 KB | Output is correct |
5 | Correct | 6 ms | 2432 KB | Output is correct |
6 | Correct | 6 ms | 2432 KB | Output is correct |
7 | Correct | 6 ms | 2432 KB | Output is correct |
8 | Correct | 6 ms | 2432 KB | Output is correct |
9 | Correct | 6 ms | 2432 KB | Output is correct |
10 | Correct | 6 ms | 2432 KB | Output is correct |
11 | Correct | 6 ms | 2560 KB | Output is correct |
12 | Correct | 9 ms | 4596 KB | Output is correct |
13 | Correct | 9 ms | 4628 KB | Output is correct |
14 | Correct | 6 ms | 2560 KB | Output is correct |
15 | Correct | 6 ms | 2560 KB | Output is correct |
16 | Correct | 6 ms | 2560 KB | Output is correct |
17 | Correct | 7 ms | 2688 KB | Output is correct |
18 | Correct | 6 ms | 2560 KB | Output is correct |
19 | Correct | 6 ms | 2432 KB | Output is correct |
20 | Correct | 58 ms | 34812 KB | Output is correct |
21 | Correct | 6 ms | 2432 KB | Output is correct |
22 | Correct | 7 ms | 2560 KB | Output is correct |
23 | Correct | 6 ms | 2560 KB | Output is correct |
24 | Correct | 7 ms | 2688 KB | Output is correct |
25 | Correct | 7 ms | 2688 KB | Output is correct |
26 | Correct | 66 ms | 35516 KB | Output is correct |
27 | Correct | 62 ms | 35516 KB | Output is correct |
28 | Correct | 8 ms | 2688 KB | Output is correct |
29 | Correct | 8 ms | 3328 KB | Output is correct |
30 | Correct | 7 ms | 2816 KB | Output is correct |
31 | Correct | 7 ms | 2944 KB | Output is correct |
32 | Correct | 7 ms | 2816 KB | Output is correct |
33 | Correct | 9 ms | 3968 KB | Output is correct |
34 | Correct | 10 ms | 3968 KB | Output is correct |
35 | Correct | 16 ms | 4480 KB | Output is correct |
36 | Correct | 7 ms | 2688 KB | Output is correct |
37 | Correct | 18 ms | 6016 KB | Output is correct |
38 | Correct | 19 ms | 5504 KB | Output is correct |
39 | Correct | 19 ms | 5760 KB | Output is correct |
40 | Correct | 19 ms | 5632 KB | Output is correct |
41 | Correct | 20 ms | 5504 KB | Output is correct |
42 | Runtime error | 336 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
43 | Halted | 0 ms | 0 KB | - |