Submission #565291

#	Time	Username	Problem	Language	Result	Execution time	Memory
565291		1ne	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	730 ms	5460 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
struct dsu{
	vector<int>parent,sz;
	void build(int n){
		parent.resize(n);
		sz.resize(n);
		for (int i = 0;i<n;++i){
			parent[i] = i;
			sz[i] = 1;
		}
	}
	int findset(int v){
		if (v == parent[v])return v;
		parent[v] = findset(parent[v]);
		return parent[v];
	}
	bool unionset(int a,int b){
		int u = findset(a);
		int v = findset(b);
		if (u == v) return false;
		if (sz[v]>sz[u])swap(u,v);
		parent[v] = u;
		sz[u]+=sz[v];
		return true;
	}
};
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,m;cin>>n>>m;
	vector<pair<int,int>>arr(m);
	vector<set<int>>brr(n);
	for (int i = 0;i<m;++i){
		cin>>arr[i].first>>arr[i].second;
		brr[arr[i].first].insert(arr[i].second);
	}
	queue<int>q;
	q.push(arr[0].first);
	vector<int>dist(n,(int)1e9);
	dist[arr[0].first] = 0;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for (auto x:brr[u]){
			for (int k = 1;u - k*x>=0;++k){
				if (dist[u - k*x] > dist[u] + k){
					dist[u - k*x] = dist[u] + k;
					q.push(u - k*x);
				}
			}
			for (int k = 1;u + k*x<n;++k){
				if (dist[u + k*x] > dist[u] + k){
					dist[u + k*x] = dist[u] + k;
					q.push(u + k*x);
				}
			}
		}
	}
	if (dist[arr[1].first]==1e9){
		dist[arr[1].first]=-1;
	}
	cout<<dist[arr[1].first]<<'\n';
	return 0;
}

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