Submission #1275727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275727		random_user27	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1094 ms	26384 KiB

skyscraper

// In The Name Of God

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define pb push_back
#define endl '\n'
#define test(x) cout<<x,exit(0)
#define fast (ios_base::sync_with_stdio(false),cin.tie(NULL))

const int maxn=3e4+10;
const int inf=1e9;
const int sq=200;
int is_have[maxn][sq+5];
int dis[maxn];
int mark[maxn];
vector<int>vec[maxn];
int n,m;


int main(){
	fast;
	cin>>n>>m;
	int start,en;
	for(int i=1;i<=m;i++){
		int b,p;cin>>b>>p;
		if(i==1){
			start=b;
		}
		if(i==2){
			en=b;
		}
		vec[b].pb(p);
		if(p<=sq){
			is_have[b][p]=1;
		}
	}
	priority_queue<pii, vector<pii>, greater<pii>> st;
	for(int i=0;i<n;i++){
		dis[i]=inf;
	}
	dis[start]=0;
	st.push({0,start});
	while(st.size()>0){
		int v=st.top().second;
		st.pop();
		if(mark[v]==1){
			continue;
		}
		mark[v]=1;
		for(int i=0;i<vec[v].size();i++){
			int p=vec[v][i];
			if(p>sq){
				for(int j=v+p;j<n;j+=p){
					if(dis[v]+(j-v)/p<dis[j]){
						dis[j]=dis[v]+(j-v)/p;
						st.push({dis[j],j});
					}
				}
				for(int j=v-p;j>=0;j-=p){
					if(dis[v]+(v-j)/p<dis[j]){
						dis[j]=dis[v]+(v-j)/p;
						st.push({dis[j],j});
					}
				}
			}
			else{
				for(int j=v+p;j<n;j+=p){
					if(dis[v]+(j-v)/p<dis[j]){
						dis[j]=dis[v]+(j-v)/p;
						st.push({dis[j],j});
					}
					if(is_have[j][p]==1){
						break;
					}
				}
				for(int j=v-p;j>=0;j-=p){
					if(dis[v]+(v-j)/p<dis[j]){
						dis[j]=dis[v]+(v-j)/p;
						st.push({dis[j],j});
					}
					if(is_have[j][p]==1){
						break;
					}
				}
			}
		}
	}
	if(dis[en]>1e7){
		cout<<-1<<endl;
	}
	else{
		cout<<dis[en]<<endl;
	}
}

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