Submission #518410

#	Time	Username	Problem	Language	Result	Execution time	Memory
518410		CodeTiger927	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	1 ms	460 KiB

skyscraper

using namespace std;

#include <iostream>
#include <bitset>
#include <queue>
#include <vector>

#define MAXN 3005

int N,M,pos[MAXN],po[MAXN];
bitset<MAXN> vis[MAXN],vis2;
queue<pair<int,pair<int,int>>> q;
vector<int> v[MAXN];

void insert(int dist,int x,int p) {
	if(~p && !vis[x][p]) q.push({dist,{x,p}});
	if(vis2[x]) return;
	vis2[x] = true;
	for(int u : v[x]) {
		if(vis[x][u]) continue;
		vis[x][u] = true;
		q.push({dist,{x,u}});
	}
	return;
}

bool within(int n) {
	return (n >= 0 && n < N);
}

int main() {
	cin >> N >> M;
	for(int i = 0;i < M;++i) {
		cin >> pos[i] >> po[i];
		v[pos[i]].push_back(po[i]);
	}
	insert(pos[0],0,-1);
	while(!q.empty()) {
		auto [u,v] = q.front();
		auto [a,b] = v;
		// cout << u << " " << a << " " << b << endl;
		q.pop();
		if(a == pos[1]) {
			cout << u << endl;
			return 0;
		}
		if(within(a - b)) insert(u + 1,a - b,b);
		if(within(a + b)) insert(u + 1,a + b,b);
	}
	cout << -1 << endl;
}

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