# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
420096 | Dymo | Jakarta Skyscrapers (APIO15_skyscraper) | C++17 | 1035 ms | 62124 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn=3e4+10;
const ll mod =1e9+7 ;
const ll base=500;
ll b[maxn];
ll p[maxn];
ll dp[maxn][base+3];
bool dd[maxn];
vector<ll> adj[maxn];
vector<ll> adj1[maxn];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp", "r"))
{
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
ll n, m ;
cin>> n>> m;
ll st;
ll ed;
for (int i=1;i<=m;i++)
{
cin>>b[i]>>p[i];
b[i]++;
if (i==1) st=b[i];
if (i==2) ed=b[i];
if (p[i]<=base)
{
adj[b[i]].pb(p[i]);
}
else
{
adj1[b[i]].pb(p[i]);
}
}
priority_queue<pair<ll,pll>,vector<pair<ll,pll>>, greater<pair<ll,pll>>> q;
for (int i=1;i<=n;i++) for (int j=0;j<=base;j++) dp[i][j]=1e9;
dp[st][0]=0;
q.push(make_pair(dp[st][0],make_pair(st,0)));
while (!q.empty())
{
auto p=q.top();
q.pop();
if (p.ff!=dp[p.ss.ff][p.ss.ss]) continue;
ll t=p.ss.ss;
ll u=p.ss.ff;
if (!dd[u])
{
dd[u]=1;
for (auto to:adj[u])
{
if (dp[u][to]>dp[u][t])
{
dp[u][to]=dp[u][t];
q.push(make_pair(dp[u][to],make_pair(u,to)));
}
}
for (auto to:adj1[u])
{
for (int j=(u%to ? u%to : to);j<=n;j+=to)
{
if (dp[j][0]>dp[u][t]+abs(u-j)/to)
{
dp[j][0]=dp[u][t]+abs(u-j)/to;
q.push(make_pair(dp[j][0],make_pair(j,0)));
}
}
}
}
for (int j=-1;j<=1;j+=2)
{
ll nxt=u+j*t;
if (nxt>=1&&nxt<=n&&dp[nxt][t]>dp[u][t]+1)
{
dp[nxt][t]=dp[u][t]+1;
q.push(make_pair(dp[nxt][t],make_pair(nxt,t)));
}
}
}
ll h=1e9;
for (int j=0;j<=base;j++) h=min(h,dp[ed][j]);
if (h==1e9) h=-1;
cout <<h<<endl;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |