# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
705334 | 2023-03-04T03:39:06 Z | ToroTN | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 2 ms | 2416 KB |
#include<bits/stdc++.h> using namespace std; #define X first #define Y second #define pb push_back int n,m,x,y,st,ed,cnt,go,cost,u,d[30005]; set<int> s[30005]; vector<pair<int,int> > v[30005]; priority_queue<pair<int,int> > pq; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); if(i==1)st=x; if(i==2)ed=x; s[x].insert(y); } for(int i=0;i<n;i++) { for(auto it=s[i].begin();it!=s[i].end();it++) { cnt=0; for(int j=i-(*it);j>=0;j-=(*it)) { ++cnt; v[i].pb({j,cnt}); if(s[j].find(*it)!=s[j].end())break; } cnt=0; for(int j=i+(*it);j<n;j+=(*it)) { ++cnt; v[i].pb({j,cnt}); if(s[j].find(*it)!=s[j].end())break; } } } for(int i=0;i<n;i++)d[i]=1e9; d[st]=0; pq.push({0,st}); while(!pq.empty()) { u=pq.top().Y; pq.pop(); for(int i=0;i<v[u].size();i++) { y=v[u][i].X,cost=v[u][i].Y; if(d[u]+cost<d[y]) { d[y]=d[u]+cost; pq.push({-d[y],y}); } } } printf("%d\n",d[ed]); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2388 KB | Output is correct |
2 | Correct | 2 ms | 2388 KB | Output is correct |
3 | Correct | 1 ms | 2388 KB | Output is correct |
4 | Incorrect | 2 ms | 2388 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2388 KB | Output is correct |
2 | Correct | 1 ms | 2380 KB | Output is correct |
3 | Correct | 1 ms | 2416 KB | Output is correct |
4 | Incorrect | 1 ms | 2388 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2388 KB | Output is correct |
2 | Correct | 2 ms | 2388 KB | Output is correct |
3 | Correct | 2 ms | 2388 KB | Output is correct |
4 | Incorrect | 2 ms | 2388 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2388 KB | Output is correct |
2 | Correct | 1 ms | 2412 KB | Output is correct |
3 | Correct | 2 ms | 2416 KB | Output is correct |
4 | Incorrect | 2 ms | 2388 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2388 KB | Output is correct |
2 | Correct | 2 ms | 2388 KB | Output is correct |
3 | Correct | 1 ms | 2388 KB | Output is correct |
4 | Incorrect | 1 ms | 2416 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |