제출 #868591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
868591		amirhoseinfar1385	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1045 ms	94156 KiB

skyscraper

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

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

void solve(){
	vector<pair<int,pair<int,int>>>di;
	for(auto x:st[av]){
		di.push_back(make_pair(0,make_pair(av,x)));
	}
	while((int)di.size()!=0){
		vector<pair<int,pair<int,int>>>fake;
		for(auto x:di){
			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;
			}
			fake.push_back(make_pair(x.first+1,make_pair(x.second.first-x.second.second,x.second.second)));
			fake.push_back(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]){
				fake.push_back(make_pair(x.first+1,make_pair(x.second.first-y,y)));
				fake.push_back(make_pair(x.first+1,make_pair(x.second.first+y,y)));
			}
			st[x.second.first].clear();
		}
		swap(di,fake);
	}
}

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