Submission #45214

#	Time	Username	Problem	Language	Result	Execution time	Memory
45214		ckodser	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1061 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=3e4+10;
const ll mod=1e9+7;
const ll inf=1e9+500;
const ll rad=100;
const ll maxm=maxn*(rad)*3+50;

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

ll cn;
vector<pair<ll,bool> > ger[maxm];
bitset<maxm> h;


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));
		}
	}

	cn=m+n*2*rad+1;

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




	deque<pii>dk;
	dk.pb(mp(0,1));
	while(dk.size()){
		ll v=dk.front().F;
		ll w=dk.front().S;
		dk.pop_front();
		if(!h[v]){
			if(v==1){
				cout<<w-1;
				return 0;
			}
			h[v]=1;
			for(auto e:ger[v]){
				if(e.S){
					dk.push_back(mp(e.F,w+1));
				}else{
					dk.push_front(mp(e.F,w));
				}
			}
		}
	}
	cout<<-1;
}

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