Submission #45208

#	Time	Username	Problem	Language	Result	Execution time	Memory
45208		ckodser	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	1110 ms	262144 KiB

skyscraper

#include<bits/stdc++.h>

#define ll	int 
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=2010;
const ll mod=1e9+7;
const ll inf=1e9+500;
const ll rad=2010;
const ll maxm=maxn*(rad)*2+50;

ll b[maxn];
ll p[maxn];
vector<ll> vec[maxn];

vector<pair<ll,short> > ger[maxm];
ll h[maxm];


int main(){

	ll n,m;
	cin>>n>>m;
	for(ll i=0;i<m;i++){
		cin>>b[i]>>p[i];
		vec[b[i]].pb(i);
	}
	for(ll i=0;i<n;i++){
		for(auto v:vec[i]){
			ger[i+m].pb(mp(v,0));
		}
	}	


	for(ll j=1;j<rad;j++){
		for(ll i=0;i<n;i++){
			ger[m+j*n+i].pb(mp(i+m,0));
			if(i>=j){
				ger[m+j*n+i].pb(mp(m+j*n+i-j,1));
			}
		}
	}
	for(ll j=1;j<rad;j++){
		for(ll i=0;i<n;i++){
			ll v=m+rad*n+(j-1)*n+i;
			ger[v].pb(mp(i+m,0));
			if(i+j<n){
				ger[v].pb(mp(v+j,1));
			}
		}
	}
	for(ll i=0;i<m;i++){
		if(p[i]<rad){
			ll v=b[i];
			ger[i].pb(mp(m+n*p[i]+v,0));
			ger[i].pb(mp(m+rad*n+(p[i]-1)*n+v,0));
		}
	}

	for(ll i=0;i<m;i++){
		if(p[i]>=rad){
			for(ll j=b[i]+p[i];j<n;j+=p[i]){
				ger[i].pb(mp(j+m,(j-b[i])/p[i]));
			}
			for(ll j=b[i]-p[i];j>=0;j-=p[i]){
				ger[i].pb(mp(j+m,(b[i]-j)/p[i]));
			}	
		}		
	}
	deque<pii> dk;
	dk.pb(mp(1,0));
	while(dk.size()){
		ll v=dk.front().S;
		ll w=dk.front().F;
		dk.pop_front();
		if(h[v]==0){
			h[v]=w;
			for(auto e:ger[v]){
				if(e.S){
					dk.pb(mp(w+1,e.F));
				}else{
					dk.push_front(mp(w,e.F));
				}
			}
		}
	}
	/*
	   set<pii> st;
	   set<pii> :: iterator it;
	   st.insert(mp(1,0));
	   while(st.size()){
	   it=st.begin();
	   ll v=(*it).S;
	   ll w=(*it).F;
	   st.erase(it);
	   if(h[v]==0){
	   h[v]=w;
	   for(auto e:ger[v]){
	   st.insert(mp(e.S+w,e.F));
	   }
	   }
	   }*/
	if(h[1]==0){
		cout<<-1;
	}else{
		cout<<h[1]-1;
	}
}
/*    
	  .      _______    __    ___     ________      ________       _________     _________   ________
	  .     /       \  |  |  /  /    /        \    |        \     /         \   |        |  |   __   \
	  .    /   _____/  |  | /  /    /    ___   \   |   ___   \   |   _______/   |  ______|  |  |  \   \
	  .   /   /        |  |/  /    /    /   \   \  |  |   \   \  |  (______     |  |_____   |  |__/   /
	  .   |  |         |     /     |   /     \  |  |  |    |  |   \        \    |        |  |      __/
	  .   |  |         |     \     |   \     /  |  |  |    |  |    \______  \   |  ______|  |      \
	  .   \   \_____   |  |\  \    \    \___/   /  |  |___/   /    _______) |   |  |_____   |   |\  \
	  .    \        \  |  | \  \    \          /   |         /    /         /   |        |  |   | \  \
	  .     \_______/  |__|  \__\    \________/    |________/     \________/    |________|  |___|  \__\
 */

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