Submission #563160

#	Time	Username	Problem	Language	Result	Execution time	Memory
563160		SeDunion	Toll (BOI17_toll)	C++17	100 / 100	278 ms	189632 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;

int k;

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] = inf;
	for (int i = 0 ; i < k ; ++ i) for (int j = 0 ; j < k ; ++ j) for (int l = 0 ; l < k ; ++ l) {
		c[i][j] = min(c[i][j], a[i][l] + b[l][j]);
	}
	return c;
}

const int LOG = 18;

mat sp[N][LOG];

mat compute(int l, int r) {
	mat cur; for (int i = 0 ; i < K ; ++ i) for (int j = 0 ; j < K ; ++ j) cur[i][j] = inf;
	bool st = false;
	int len = r - l + 1;
	cerr << l << " " << r << " sdf\n";
	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 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) - 1 < 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;
		cerr << qa[i] << " " << qb[i] << "|" << ba << " " << bb << "|" << ia << " " << ib << endl;
		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 - 2;
			mid = compute(l, r);
			for (int s = 0 ; s < k ; ++ s) {
				for (int t = 0 ; t < k ; ++ t) {
					cerr << mid[s][t] << " ";
					ans = min(ans, (ba == bb - 2 && s == t ? 0 : mid[s][t]) + g[ba][ia][s] + g[bb - 1][t][ib]);
				}
				cerr << endl;
			}
		}
		if (ans >= inf) ans = -1;
		cout << ans << "\n";
	}
}

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