Submission #1202686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202686		hackstar	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	22 / 100	6 ms	2632 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
const long long inf=1e18;
typedef unsigned long long ull;

struct pair_hash{
	static ull splitmix64(ull x){
		x+=0x9e3779b97f4a7c15;
		x=(x^(x>>30))*0xbf58476d1ce4e5b9;
		x=(x^(x>>27))*0x94d049bb133111eb;
		return x^(x>>31);
	}
	size_t operator()(const pair<int,int>&p)const{
		static const ull r=chrono::steady_clock::now().time_since_epoch().count();
		ull k=(ull(p.first)<<32)|unsigned(p.second);
		return splitmix64(k+r);
	}
};

void solve(){
	int n,m;
	cin>>n>>m;
	vector<pair<int,int>>a(m);
	for(int i=0;i<m;i++){
		cin>>a[i].first>>a[i].second;
	}
	vector<vector<int>>in(n);
	for(int i=0;i<m;i++){
		in[a[i].first].push_back(i);
	}
	vector<int>pos(2);
	pos[0]=a[0].first;pos[1]=a[1].first;
	unordered_map<pair<int,int>,int,pair_hash>dp;
	unordered_set<pair<int,int>,pair_hash>vis;
	dp.reserve(n*2);vis.reserve(n*2);
	auto dfs=[&](auto self,int id,int power)->int{
		if(id==pos[1])return 0;
		auto key=make_pair(id,power);
		if(dp.count(key))return dp[key];
		if(vis.count(key))return inf;
		vis.insert(key);
		int best=inf;
		if(id+power>=0&&id+power<n){
			int r=self(self,id+power,power);
			if(r<inf)best=min(best,r+1);
		}
		if(id-power>=0&&id-power<n){
			int r=self(self,id-power,power);
			if(r<inf)best=min(best,r+1);
		}
		for(int idx:in[id]){
			int np=a[idx].second;
			if(np==power)continue;
			int r=self(self,id,np);
			if(r<inf)best=min(best,r);
		}
		vis.erase(key);
		return dp[key]=best;
	};
	int ans=dfs(dfs,pos[0],a[0].second);
	cout<<(ans>=inf?-1:ans)<<"\n";
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int t=1;
	while(t--)solve();
	return 0;
}

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