제출 #162635

#제출 시각아이디문제언어결과실행 시간메모리
162635HungAnhGoldIBO2020Jakarta Skyscrapers (APIO15_skyscraper)C++14
0 / 100
224 ms262148 KiB
#include<bits/stdc++.h> using namespace std; const int N=3e4+2; const int magic=175; const int wow=2e7+2; const int inf=1e9+7; const int LIM=N*magic+N; vector<int> lis[wow]; 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; 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 la cac nut dai dien - NO //m+n -> m+n*magic la cac nut dai dien cho cac luong van tai for(i=1;i<=min(magic,n-1);i++){ for(j=0;j<n-i;j++){ k=i*n+j+m; l=i*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<=min(n-1,magic);j++){ k=j*n+b[i]+m; adj[k].push_back({i,0}); } if(p[i]>min(magic,n-1)){ 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]*n+b[i]+m; adj[i].push_back({k,0}); } } for(i=1;i<=m+magic*n;i++){ dis[i]=inf; } dis[0]=0; // 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:94:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(k=0;k<adj[j].size();k++){
            ~^~~~~~~~~~~~~~
#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...