# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
236144 | 2020-05-31T09:38:09 Z | thtsshz_bgwrswh | Jakarta Skyscrapers (APIO15_skyscraper) | C++17 | 7 ms | 2472 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]){ if(s[j].count(power[i])) break; //printf("%d\n",j); g[pos[i]].emplace_back(j,(j-pos[i])/power[i]); } for(j=pos[i]-power[i];j>=0;j-=power[i]){ if(s[j].count(power[i])) break; g[pos[i]].emplace_back(j,(pos[i]-j)/power[i]); } // 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 | 2304 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 | Incorrect | 6 ms | 2368 KB | Output isn't 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 | Incorrect | 5 ms | 2432 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 2432 KB | Output is correct |
2 | Correct | 5 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 | Incorrect | 6 ms | 2432 KB | Output isn't correct |
8 | 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 | Incorrect | 6 ms | 2432 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2432 KB | Output is correct |
2 | Correct | 7 ms | 2472 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 | Incorrect | 6 ms | 2432 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |