# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
207090 | 2020-03-06T11:30:24 Z | Sa1loum | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 22 ms | 23832 KB |
#include <bits/stdc++.h> using namespace std; #define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define mem(a,b) memset(a, b, sizeof(a)) #define F first #define S second #define Si size() #define pb(x) push_back(x) typedef double D; typedef long long ll; typedef long double ld; const int MOD=(int)1e9+7,MAX=(int)1e6+10; ll n,m,b[MAX],p[MAX],vis[MAX]; vector <pair<ll,ll> > v[MAX]; int main() { scanf("%lld%lld",&n,&m); for (int i=0;i<m;i++) { scanf("%lld%lld",&b[i],&p[i]); ll d=0; for (int j=b[i],k=b[i];;j+=p[i],k-=p[i]) { bool flag=0; if (0<=j && j<n) { flag=1; if (j!=b[i]) { v[b[i]].push_back({j,d}); } } if (0<=k && k<n) { flag=1; if (k!=b[i]) { v[b[i]].push_back({k,d}); } } d++; if (!flag) break; } } priority_queue <pair<ll,ll>> pq; pq.push({0,0}); while (!pq.empty()) { ll x=pq.top().S; ll w=-pq.top().F; pq.pop(); if (vis[x]) continue; vis[x]=1; if (x==1) {printf("%lld\n",w); return 0;} for (auto it:v[x]) { if (vis[it.F]) continue; pq.push({-w-it.S,it.F}); } } puts("-1\n"); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 23800 KB | Output is correct |
2 | Incorrect | 20 ms | 23800 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 23800 KB | Output is correct |
2 | Incorrect | 21 ms | 23832 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 23800 KB | Output is correct |
2 | Incorrect | 20 ms | 23672 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 23800 KB | Output is correct |
2 | Incorrect | 22 ms | 23800 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 23800 KB | Output is correct |
2 | Incorrect | 20 ms | 23800 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |