Submission #1130943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130943		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<set>
const int inf = 1e9;
const int mxn = 3e4 + 5;
const int sl = 174;
using namespace std;
vector<int> g[mxn];
set<vector<int>> q; //{dist, pos, power}
vector<vector<int>> dist;

void vis(int i, int p, int c) {
	if (dist[i][p] != inf) q.erase({ dist[i][p], i, p });
	dist[i][p] = c;
	q.insert({ 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 + 1, vector<int>(sq + 1, inf));
	q.insert({ 0, s, 0 });
	dist[s][0] = 0;

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

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