# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
207054 | 2020-03-06T09:00:53 Z | Sa1loum | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 21 ms | 23868 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]); 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,abs(j-b[i])/p[i]}); //v[j].push_back({b[i],abs(j-b[i])/p[i]}); } } if (0<=k && k<n) { flag=1; if (k!=b[i]) { v[b[i]].push_back({k,abs(k-b[i])/p[i]}); //v[k].push_back({b[i],abs(k-b[i])/p[i]}); } } if (!flag) break; } } priority_queue <pair<ll,ll>> pq; pq.push({0,0}); while (!pq.empty()) { ll x=pq.top().F; ll w=-pq.top().S; pq.pop(); if (vis[x]) continue; vis[x]=1; if (x==1) {cout<<w; return 0;} for (auto it:v[x]) { if (vis[it.F]) continue; pq.push({it.F,-w-it.S}); } } cout<<-1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 23800 KB | Output is correct |
2 | Incorrect | 20 ms | 23800 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 23800 KB | Output is correct |
2 | Incorrect | 20 ms | 23800 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 23800 KB | Output is correct |
2 | Incorrect | 21 ms | 23800 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 23800 KB | Output is correct |
2 | Incorrect | 19 ms | 23800 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 23800 KB | Output is correct |
2 | Incorrect | 20 ms | 23868 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |