Submission #882795

#	Time	Username	Problem	Language	Result	Execution time	Memory
882795		Kel_Mahmut	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	161 ms	69808 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, pos, sped;
bool vis[maxn][maxn];
vector<int> v[maxn];
queue<array<int, 3>> q;

void pushq(int u, int s, int 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, pos = b;
		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());
	}

	q.push({pos, sped, 0});
	while(!q.empty()){
		auto [u, s, dst] = q.front(); q.pop();
		if(target == u) cout << dst, exit(0);
		if(vis[u][s]) 
			continue;
		vis[u][s] = 1;
		for(int sp : v[u])
			pushq(u, sp, dst+1);
		pushq(u, s, dst+1);
	}

	cout << -1;
}

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