Submission #868588

#	Time	Username	Problem	Language	Result	Execution time	Memory
868588		amirhoseinfar1385	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1060 ms	55640 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
const int maxn=30000+10;
int n,m,vis[maxn],dis[maxn],av;
set<int>st[maxn],fst[maxn];
vector<int>adj[maxn];

void upd(int ind,int p){
	if(st[ind].count(p)!=0){
		return ;
	}
	st[ind].insert(p);
	fst[ind].insert(p);
	for(int i=ind-p;i>=0;i-=p){
		adj[i].push_back(i+p);
		adj[i+p].push_back(i);
		fst[i].insert(p);
	}
	for(int i=ind+p;i<n;i+=p){
		adj[i].push_back(i-p);
		adj[i-p].push_back(i);
		fst[i].insert(p);
	}
}

void solve(){
	set<pair<int,pair<int,int>>>di;
	for(auto x:st[av]){
		di.insert(make_pair(0,make_pair(av,x)));
	}
	while((int)di.size()!=0){
		auto x=*di.begin();
		di.erase(x);
		if(x.second.first<0||x.second.first>=n){
			continue;
		}
		if(fst[x.second.first].count(x.second.second)==0){
			continue;
		}
		if(vis[x.second.first]==0){
			vis[x.second.first]=1;
			dis[x.second.first]=x.first;
		}
		di.insert(make_pair(x.first+1,make_pair(x.second.first-x.second.second,x.second.second)));
		di.insert(make_pair(x.first+1,make_pair(x.second.first+x.second.second,x.second.second)));
		fst[x.second.first].erase(x.second.second);
		for(auto y:st[x.second.first]){
			di.insert(make_pair(x.first+1,make_pair(x.second.first-y,y)));
			di.insert(make_pair(x.first+1,make_pair(x.second.first+y,y)));
		}
		st[x.second.first].clear();
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	int s=0;
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		upd(u,v);
		if(i==1){
			s=u;
		}
		if(i==0){
			av=u;
		}
	}
	solve();
	if(vis[s]){
		cout<<dis[s]<<"\n";
	}
	else{
		cout<<-1<<"\n";
	}
}

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