이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector")
using namespace std;
const int N=3e4+2;
const int magic=202;
const int inf=1e9+7;
const int LIM=N*magic;
vector<int> lis[N*10];
int b[N],p[N],dis[LIM],lst[N];
bool ok[N];
vector<pair<int,int> > adj[LIM];
//priority_queue<pair<int,int> > lis;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m,i,j,k,l;
cin>>n>>m;
int lim=min(magic,n-1);
for(i=0;i<m;i++){ //0->m-1
cin>>b[i]>>p[i];
if(ok[b[i]]){
adj[i].push_back({lst[b[i]],0});
}
lst[b[i]]=i;
ok[b[i]]=true;
}
//m -> m+(n-1)*magic la cac nut dai dien cho cac luong van tai
for(i=1;i<=lim;i++){
for(j=0;j<n-i;j++){
k=(i-1)*n+j+m;
l=(i-1)*n+j+i+m;
adj[k].push_back({l,1});
adj[l].push_back({k,1});
}
}
for(i=0;i<m;i++){
for(j=1;j<=lim;j++){
k=(j-1)*n+b[i]+m;
adj[k].push_back({i,0});
}
if(p[i]>lim){
j=b[i];
k=0;
while(j>=0){
if(ok[j]){
adj[i].push_back({lst[j],k});
}
j-=p[i];
k++;
}
j=b[i];
k=0;
while(j+p[i]<n){
j+=p[i];
k++;
if(ok[j]){
adj[i].push_back({lst[j],k});
}
}
} //the dog, not the dai dien :'(
else{
k=(p[i]-1)*n+b[i]+m;
adj[i].push_back({k,0});
}
}
for(i=1;i<=m+magic*n;i++){
dis[i]=inf;
}
// lis.push({0,0});
// while(lis.size()){
// j=-lis.top().first;
// k=lis.top().second;
// lis.pop();
// if(dis[k]==j){
// for(i=0;i<adj[k].size();i++){
// if(dis[adj[k][i].first]>dis[k]+adj[k][i].second){
// dis[adj[k][i].first]=dis[k]+adj[k][i].second;
// lis.push({-dis[adj[k][i].first],adj[k][i].first});
// }
// }
// }
// }
int cnt=1;
lis[dis[0]].push_back(0);
for(i=0;i<LIM&&cnt;i++){
while(lis[i].size()){
j=lis[i].back();
cnt--;
lis[i].pop_back();
if(dis[j]!=i){
continue;
}
for(k=0;k<adj[j].size();k++){
if(dis[adj[j][k].first]>dis[j]+adj[j][k].second){
dis[adj[j][k].first]=dis[j]+adj[j][k].second;
cnt++;
lis[dis[adj[j][k].first]].push_back(adj[j][k].first);
}
}
}
}
if(dis[1]!=inf){
cout<<dis[1];
}
else{
cout<<-1;
}
}
/*
5 3
0 2
1 1
4 1
*/
컴파일 시 표준 에러 (stderr) 메시지
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:93:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(k=0;k<adj[j].size();k++){
~^~~~~~~~~~~~~~
# | 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... |