Submission #1195747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195747		hackstar	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	22 / 100	5 ms	2192 KiB

skyscraper

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

#define int long long
#define all(x) x.begin(),x.end()

struct node{
	int id,power;	
};

const long long inf=1e18;

typedef unsigned long long ull;
static inline ull pack_key(int pos,int p) {
    return (ull(pos)<<32)|(unsigned)p;
}

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;
		cin>>a[i].second;
	}
	vector<int>pos(2);
	for(int i=0;i<2;i++){
		pos[i]=a[i].first;
	}
	auto check=[&](int id)->bool{
		if(id>=0&&id<n){
			return 1;
		}
		return 0;
	};
	vector<vector<int>>in(n);
	for(int i=0;i<m;i++){
		in[a[i].first].emplace_back(i);
	}
	unordered_map<ull,int>dp;
	unordered_set<ull>vis;
	auto dfs=[&](auto dfs,int id,int power)->int{
		if(id==pos[1]){
			return 0;
		}
		ull x=pack_key(id,power);
		if(dp.count(x)){
			return dp[x];
		}
		if(vis.count(x)){
			return inf;
		}
		vis.insert(x);
		int cur=inf;
		if(check(id+power)){
			int cur_=dfs(dfs,id+power,power);
			if(cur_==inf);
			else cur=min(cur,cur_+1);
		}
		if(check(id-power)){
			int cur_=dfs(dfs,id-power,power);
			if(cur_==inf);
			else cur=min(cur,cur_+1);
		}
		for(auto x:in[id]){
			if(a[x].second==power){
				continue;
			}
			int cur_=dfs(dfs,id,a[x].second);
			if(cur_==inf);
			else cur=min(cur,cur_);
		}
		vis.erase(x);
		return dp[x]=cur;
	};
	int x=dfs(dfs,pos[0],a[0].second);
	cout<<(x>=inf?-1:x);
}

signed main(){
	int t=1;
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	//cin>>t;
	while(t--){
		solve();
	}
}

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