Submission #667153

#	Time	Username	Problem	Language	Result	Execution time	Memory
667153		flappybird	Toll (BOI17_toll)	C++17	100 / 100	655 ms	332016 KiB

toll

#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 50505
#define MAXS 17
#define INF 10000000000000
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MK 5
vector<vector<ll>> sp[MAX][MAXS];
int K;
vector<vector<ll>> operator+(vector<vector<ll>>& v1, vector<vector<ll>>& v2) {
	vector<vector<ll>> res = vector<vector<ll>>(K, vector<ll>(K, INF));
	int i, j, k;
	for (i = 0; i < K; i++) for (j = 0; j < K; j++) for (k = 0; k < K; k++) res[i][j] = min(res[i][j], v1[i][k] + v2[k][j]);
	return res;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M, Q;
	cin >> K >> N >> M >> Q;
	int i, j;
	int X = (N + K - 1) / K;
	for (i = 0; i < MAX; i++) for (j = 0; j < MAXS; j++) sp[i][j] = vector<vector<ll>>(K, vector<ll>(K, INF));
	int a, b, c;
	for (i = 1; i <= M; i++) {
		cin >> a >> b >> c;
		sp[a / K][0][a % K][b % K] = c;
	}
	for (j = 1; j < MAXS; j++) for (i = 0; i <= X; i++) if (i + (1 << (j - 1)) <= X + 1) sp[i][j] = sp[i][j - 1] + sp[i + (1 << (j - 1))][j - 1];
	while (Q--) {
		cin >> a >> b;
		int aa = a;
		int d = b / K - a / K;
		if (!d) {
			cout << -1 << ln;
			continue;
		}
		a /= K;
		vector<vector<ll>> v;
		for (i = 0; i < MAXS; i++) {
			if (d >> i & 1) {
				if (v.empty()) v = sp[a][i];
				else v = v + sp[a][i];
				a += 1 << i;
			}
		}
		ll ans = v[aa % K][b % K];
		if (ans >= INF) cout << -1 << ln;
		else cout << ans << ln;
	}
}

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