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;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 3e4;
const int INF = 1e9;
int N, M, S, E;
vector<int> A[MAXN+10];
vector<pii> adj[MAXN+10];
int dist[MAXN+10];
struct Queue
{
int u, w;
bool operator < (const Queue &p) const { return w>p.w; }
};
int main()
{
int i, j, k;
scanf("%d%d", &N, &M);
for(i=1; i<=M; i++)
{
int b, p;
scanf("%d%d", &b, &p);
if(i==1) S=b;
if(i==2) E=b;
A[p].push_back(b);
}
for(i=1; i<=MAXN; i++)
{
if(A[i].empty()) continue;
vector<vector<int>> V;
vector<int> comp;
V.resize(i);
for(auto it : A[i]) V[it%i].push_back(it);
for(auto it : A[i]) comp.push_back(it%i);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
for(auto it : comp)
{
sort(V[it].begin(), V[it].end());
for(j=1; j<V[it].size(); j++)
{
int now=V[it][j], bef=V[it][j-1];
for(k=bef+i; k<=now; k+=i) adj[bef].push_back({k, (k-bef)/i});
for(k=now-i; k>=bef; k-=i) adj[now].push_back({k, (now-k)/i});
}
for(k=V[it].back()+i; k<N; k+=i) adj[V[it].back()].push_back({k, (k-V[it].back())/i});
for(k=V[it][0]-i; k>=0; k-=i) adj[V[it][0]].push_back({k, (V[it][0]-k)/i});
}
}
priority_queue<Queue> PQ;
for(i=0; i<N; i++) dist[i]=INF;
PQ.push({S, 0}); dist[S]=0;
while(!PQ.empty())
{
Queue now=PQ.top(); PQ.pop();
if(dist[now.u]<now.w) continue;
for(auto nxt : adj[now.u]) if(dist[nxt.first]>now.w+nxt.second) PQ.push({nxt.first, now.w+nxt.second}), dist[nxt.first]=now.w+nxt.second;
}
if(dist[E]==INF) dist[E]=-1;
printf("%d\n", dist[E]);
}
Compilation message (stderr)
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:51:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=1; j<V[it].size(); j++)
~^~~~~~~~~~~~~
skyscraper.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &b, &p);
~~~~~^~~~~~~~~~~~~~~~
# | 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... |