제출 #162662

#제출 시각아이디문제언어결과실행 시간메모리
162662HungAnhGoldIBO2020Jakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
829 ms262144 KiB
#include<bits/stdc++.h> #pragma GCC optimize("Ofast,no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") using namespace std; const int N=3e4; const int inf=1e9+7; const int LIM=N*174; //vector<int> lis[N<<1]; 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=0; cin>>n>>m; 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}); } l=max(l,p[i]); lst[b[i]]=i; ok[b[i]]=true; } int magic=sqrt(l)+1; int lim=min(magic,n-1); //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}); } } fill(dis+1,dis+LIM,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:75:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<adj[k].size();++i){
            ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...