Submission #648433

#	Time	Username	Problem	Language	Result	Execution time	Memory
648433		ymm	Toll (BOI17_toll)	C++17	100 / 100	2411 ms	7012 KiB

toll

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

typedef unsigned int vec __attribute__((vector_size(32), aligned(4)));
const int N = 50'016;
vec toll[N];
vec mask[N];
unsigned int dis[N];
int n, m, k, o;

#define SMIN(x, y) ((x)=(x)<(y)?(x):(y))

int order(int v, int u)
{
	const int k = ::k;
	fill(dis+v, dis+u+1, (1u<<31)-1);
	dis[v] = 0;
	while (v%k) {
		SMIN(*(vec *)(dis + v+k-v%k), (dis[v] + toll[v]) | mask[v]);
		++v;
	}
	const int vk = v/k; // vulkan
	const int uk = u/k; // united kingdom
	Loop (i,vk,uk) {
		const int ki = i*k;
		Loop (x,0,k) {
			SMIN(*(vec *)(dis+ki+k), 
			     (dis[ki+x] + toll[ki+x]) | mask[ki+x]);
		}
	}
	return dis[u] == (1u<<31)-1? -1: dis[u];
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	fill(mask, mask+N, vec{~0u, ~0u, ~0u, ~0u, ~0u, ~0u, ~0u, ~0u});
	cin >> k >> n >> m >> o;
	Loop (i,0,m) {
		int v, u, w;
		cin >> v >> u >> w;
		toll[v][u%k] = w;
		mask[v][u%k] = 0;
	}
	while (o--) {
		int v, u;
		cin >> v >> u;
		cout << order(v, u) << '\n';
	};
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44