Submission #882765

#	Time	Username	Problem	Language	Result	Execution time	Memory
882765		Kel_Mahmut	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	1 ms	4700 KiB

skyscraper

#include <bits/stdc++.h>
#define all(aa) aa.begin(), aa.end()
#define pb push_back
#define endl ("\n")
typedef long long ll;
using namespace std;

const ll INF (1000000000000000);
const int maxn = 2005, maxm = 2005;

int n, m, target;
bool vis[maxn][maxn];
vector<int> v[maxn];
ll d[maxn][maxn], sped;
queue<array<ll, 3>> q;

void pushq(ll u, ll s, ll dst){
	if(u - s >= 0) q.push({u - s, s, dst});
	if(u + s < n) q.push({u+s, s, dst});
}

int main(){
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int b, p;
		cin >> b >> p;
		if(i == 0) sped = p;
		if(i != 1) v[b].pb(p);
		else target = b;
	}
	for(int i = 0; i < n; i++){
		sort(all(v[i]));
		v[i].resize(unique(all(v[i])) - v[i].begin());
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < maxn; j++)
			d[i][j] = INF;
	}
	q.push({0, sped, 0});
	while(!q.empty()){
		auto [u, s, dst] = q.front(); q.pop();
		if(vis[u][s]) 
			continue;
		vis[u][s] = 1;
		d[u][s] = dst;
		for(int sp : v[u])
			pushq(u, sp, dst+1);
		pushq(u, s, dst+1);
	}
	ll ans = INF;
	for(int i = 1; i < maxn; i++){
		ans = min(ans, d[target][i]);
	}
	if(ans == INF) cout << -1;
	else cout << ans;
}

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