Submission #162672

#	Time	Username	Problem	Language	Result	Execution time	Memory
162672		HungAnhGoldIBO2020	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	829 ms	262144 KiB

skyscraper

#include<bits/stdc++.h>
#pragma GCC optimize("O3,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){
		if(i==lst[b[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;
//					lis[dis[adj[j][k].first]].push_back(adj[j][k].first);
//					++cnt;
//				}
//			}
//		}
//	}
	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:77:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<adj[k].size();++i){
            ~^~~~~~~~~~~~~~

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