Submission #563145

#	Time	Username	Problem	Language	Result	Execution time	Memory
563145		SeDunion	Toll (BOI17_toll)	C++17	0 / 100	293 ms	186348 KiB

toll

#include <iostream>
#include <array>
#include <cassert>
#include <algorithm>
#include <string>
#include <bitset> 
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#ifndef LOCAL
	#include <bits/stdc++.h>
	#define cerr if(false)cerr
#endif
 
using namespace std;
using ll = long long;

const int N = 5e4 + 66;

const int K = 5;

using mat = array<array<ll, K>, K>;

mat g[N];

const ll inf = 1e18 + 126;

mat compute(mat a, mat b) {
	mat c; for (int i = 0 ; i < K ; ++ i) for (int j = 0 ; j < K ; ++ j) c[i][j] = (i == j ? 0 : inf);
	for (int i = 0 ; i < K ; ++ i) for (int j = 0 ; j < K ; ++ j) for (int k = 0 ; k < K ; ++ k) {
		c[i][j] = min(c[i][j], a[i][k] + b[k][j]);
	}
	return c;
}

const int LOG = 18;

mat sp[N][LOG];

mat compute(int l, int r) {
	cerr << l << " " << r << " askinh\n";
	mat cur;
	bool st = false;
	int len = r - l + 1;
	for (int i = 0 ; i < LOG ; ++ i) {
		if (len >> i & 1) {
			cerr << "[" << l << " " << l + (1 << i) - 1 << "]\n";
			if (!st) cur = sp[l][i], st = true;
			else cur = compute(cur, sp[l][i]);
			l += 1 << i;
		}
	}
	return cur;
}

mat mid;

int qa[N], qb[N];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int k, n, m, q;
	cin >> k >> n >> m >> q;
	for (int b = 0 ; b < n ; ++ b) {
		for (int i = 0 ; i < k ; ++ i) {
			for (int j = 0 ; j < k ; ++ j) {
				g[b][i][j] = inf;
			}
		}
	}
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		int ba = a / k, bb = b / k;
		assert(ba + 1 == bb);
		int ia = a % k, ib = b % k;
		g[ba][ia][ib] = c;
	}
	for (int i = 0 ; i < n ; ++ i) {
		sp[i][0] = g[i];
	}
	for (int j = 1 ; j < LOG ; ++ j) {
		for (int i = 0 ; i + (1 << j) < n ; ++ i) {
			sp[i][j] = compute(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
		}
	}
	for (int i = 0 ; i < q ; ++ i) {
		cin >> qa[i] >> qb[i];
		int ba = qa[i] / k, bb = qb[i] / k;
		int ia = qa[i] % k, ib = qb[i] % k;
		ll ans;
		if (ba == bb) {
			ans = inf;
		} else if (ba == bb - 1) {
			ans = g[ba][ia][ib];
		} else {
			ans = inf;
			int l = ba + 1, r = bb - 1;
			mid = compute(l, r);
			for (int s = 0 ; s < k ; ++ s) {
				for (int t = 0 ; t < k ; ++ t) {
					ans = min(ans, (ba == bb - 2 ? 0 : mid[s][t]) + g[ba][ia][s] + g[bb - 1][t][ib]);
				}
			}
		}
		if (ans >= inf) ans = -1;
		cout << ans << "\n";
	}
}

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