Submission #162639

#	Time	Username	Problem	Language	Result	Execution time	Memory
162639		HungAnhGoldIBO2020	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1100 ms	211120 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+2;
const int magic=175;
const int inf=1e9+7;
const int LIM=N*magic+N;
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;
	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
*/

Compilation message (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++){
            ~^~~~~~~~~~~~~~

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