# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
705335 | ToroTN | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 225 ms | 65592 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 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});
}
}
}
if(d[ed]==1e9)
{
printf("-1\n");
}else
{
printf("%d\n",d[ed]);
}
}
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... |