Submission #1130951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130951		am_aadvik	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	1 ms	1096 KiB

skyscraper

#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,sse4,sse4.2,lzcnt,popcnt")
#include <iostream>
#include<vector>
#include<math.h>
#include<queue>
const int inf = 1e9;
const int mxn = 3e4 + 5;
using namespace std;
vector<int> g[mxn];
priority_queue<vector<int>> q; //{dist, pos, power}
vector<vector<int>> dist;

void vis(int i, int p, int c) {
	if (dist[i][p] > c) {
		dist[i][p] = c;
		q.push({ c, i, p });
	}

}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int n, m, s = -1, sq, t = -1; cin >> n >> m;
	sq = sqrt(n);

	for (int i = 0; i < m; ++i) {
		int x, y; cin >> x >> y;
		if (i == 0) s = x;
		if (i == 1) t = x;
		g[x].push_back(y);
	}

	dist.assign(n, vector<int>(sq, inf));
	q.push({ 0, s, 0 });
	dist[s][0] = 0;

	while (!q.empty()) {
		auto f = q.top(); q.pop();
		if (f[1] == t) { cout << f[0]; return 0; }

		if (f[2] == 0) {
			for (auto x : g[f[1]]) {
				if (x < sq)
					vis(f[1], x, f[0]);
				else {
					if (f[1] >= x)
						for (int i = f[1] - x, v = 1; i >= 0; i -= x, ++v)
							vis(i, 0, v + f[0]);
					if ((f[1] + x) < n)
						for (int i = f[1] + x, v = 1; i < n; i += x, ++v)
							vis(i, 0, v + f[0]);
				}
			}
		}
		else {
			vis(f[1], 0, f[0]);
			if (f[1] >= f[2])
				vis(f[1] - f[2], f[2], f[0] + 1);
			if ((f[1] + f[2]) < n)
				vis(f[1] + f[2], f[2], f[0] + 1);
		}

	}
	cout << -1;
}

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