Submission #162623

#	Time	Username	Problem	Language	Result	Execution time	Memory
162623		HungAnhGoldIBO2020	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	125 ms	128036 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+2;
const int magic=180;
const int inf=1e9+7;
const int LIM=N*magic+N;
int b[N],p[N],dis[LIM];
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];
	}
	//m->m+n-1 la cac nut dai dien
	//m+n -> m+n*magic-1 la cac nut dai dien cho cac luong van tai
	for(i=1;i<=min(magic,n-1);i++){
		for(j=0;j+i<n;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(j=0;j<n;j++){
			adj[m+j].push_back({i*n+j+m,0});
		}
	}
	for(i=0;i<m;i++){
		if(p[i]>min(magic,n-1)){
			j=b[i];
			k=0;
			while(j>=0){
				adj[i].push_back({m+j,k});
				j-=p[i];
				k++;
			}
			j=b[i];
			k=0;
			while(true){
				j+=p[i];
				k++;
				if(j>=n){
					break;
				}
				adj[i].push_back({m+j,k});
			}
		}
		else{
			for(j=1;j<=min(n-1,magic);j++){
				k=j*n+b[i]+m;
				adj[k].push_back({i,0});
			}
			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});
				}
			}
		}
	}
	if(dis[1]!=inf){
		cout<<dis[1];
	}
	else{
		cout<<-1;
	}
}
/*
5 3
0 2
1 1
4 1
5
*/

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:70:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<adj[k].size();i++){
            ~^~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43