# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
383360 | 2021-03-29T18:03:59 Z | tjrwodnjs999 | Jakarta Skyscrapers (APIO15_skyscraper) | C++11 | 3 ms | 2028 KB |
#include <bits/stdc++.h> #define ll long long #define x first #define y second using namespace std; int n,m,B[30005],P[30005]; ll dist[30005]; vector<int> Map[30005],adj[30005],vt[10][10]; priority_queue<pair<ll,int>> pq; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&B[i],&P[i]); Map[B[i]].push_back(i); for(int j=1;j<10;j++) vt[j][B[i]%j].push_back(i); } for(int i=1;i<=m;i++){ if(P[i]>=10){ for(int j=B[i]+P[i];j<n;j++){ for(int k:Map[j]) adj[i].push_back(k); } for(int j=B[i]-P[i];j>=0;j--){ for(int k:Map[j]) adj[i].push_back(k); } } } fill(dist,dist+30005,1e9); dist[1]=0; pq.push({0,1}); while(!pq.empty()){ int now=pq.top().second; ll cost=-pq.top().first; pq.pop(); if(dist[now]<cost) continue; if(P[now]>=10){ for(int i:adj[now]){ ll d=abs(B[i]-B[now])/P[now]; if(dist[i]>cost+d) dist[i]=cost+d,pq.push({-dist[i],i}); } } else{ for(int i:vt[P[now]][B[now]%P[now]]){ ll d=abs(B[i]-B[now])/P[now]; if(dist[i]>cost+d) dist[i]=cost+d,pq.push({-dist[i],i}); } } } printf("%lld",dist[2]==1e9?-1:dist[2]); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2028 KB | Output is correct |
2 | Correct | 2 ms | 2028 KB | Output is correct |
3 | Correct | 2 ms | 2028 KB | Output is correct |
4 | Correct | 2 ms | 2028 KB | Output is correct |
5 | Correct | 2 ms | 2028 KB | Output is correct |
6 | Correct | 2 ms | 2028 KB | Output is correct |
7 | Correct | 2 ms | 2028 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2028 KB | Output is correct |
2 | Correct | 2 ms | 2028 KB | Output is correct |
3 | Correct | 2 ms | 2028 KB | Output is correct |
4 | Correct | 2 ms | 2028 KB | Output is correct |
5 | Correct | 2 ms | 2028 KB | Output is correct |
6 | Correct | 2 ms | 2028 KB | Output is correct |
7 | Correct | 2 ms | 2028 KB | Output is correct |
8 | Correct | 2 ms | 2028 KB | Output is correct |
9 | Incorrect | 3 ms | 2028 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2028 KB | Output is correct |
2 | Correct | 2 ms | 2028 KB | Output is correct |
3 | Correct | 2 ms | 2028 KB | Output is correct |
4 | Correct | 2 ms | 2028 KB | Output is correct |
5 | Correct | 2 ms | 2028 KB | Output is correct |
6 | Correct | 2 ms | 2028 KB | Output is correct |
7 | Correct | 2 ms | 2028 KB | Output is correct |
8 | Correct | 2 ms | 2028 KB | Output is correct |
9 | Incorrect | 2 ms | 2028 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2028 KB | Output is correct |
2 | Correct | 2 ms | 2028 KB | Output is correct |
3 | Correct | 2 ms | 2028 KB | Output is correct |
4 | Correct | 2 ms | 2028 KB | Output is correct |
5 | Correct | 2 ms | 2028 KB | Output is correct |
6 | Correct | 2 ms | 2028 KB | Output is correct |
7 | Correct | 2 ms | 2028 KB | Output is correct |
8 | Correct | 2 ms | 2028 KB | Output is correct |
9 | Incorrect | 2 ms | 2028 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2028 KB | Output is correct |
2 | Correct | 2 ms | 2028 KB | Output is correct |
3 | Correct | 2 ms | 2028 KB | Output is correct |
4 | Correct | 2 ms | 2028 KB | Output is correct |
5 | Correct | 2 ms | 2028 KB | Output is correct |
6 | Correct | 2 ms | 2028 KB | Output is correct |
7 | Correct | 2 ms | 2028 KB | Output is correct |
8 | Correct | 2 ms | 2028 KB | Output is correct |
9 | Incorrect | 2 ms | 2028 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |