# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
236048 | 2020-05-31T03:08:32 Z | thtsshz_bgwrswh | Jakarta Skyscrapers (APIO15_skyscraper) | C++17 | 5 ms | 1024 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]; 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]); for(i=0;i<m;i++) for(j=0;j<m;j++){ if(j==i||pos[j]==pos[i]||abs(pos[j]-pos[i])%power[i]) continue; g[i].emplace_back(j,abs(pos[j]-pos[i])/power[i]); } for(i=0;i<m;i++) dis[i]=1000000000; dis[0]=0; pq.push({0,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[1]==1000000000) puts("-1"); else printf("%d\n",dis[1]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1024 KB | Output is correct |
2 | Incorrect | 5 ms | 1024 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1024 KB | Output is correct |
2 | Incorrect | 5 ms | 1024 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1024 KB | Output is correct |
2 | Incorrect | 5 ms | 1024 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1024 KB | Output is correct |
2 | Incorrect | 5 ms | 1024 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1024 KB | Output is correct |
2 | Incorrect | 5 ms | 1024 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |