제출 #548862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
548862		lorenzoferrari	Toll (BOI17_toll)	C++17	100 / 100	349 ms	83124 KiB

toll

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int INF = 1e9;
const int LOG = 17;

struct mat {
	int n;
	vector<vector<LL>> a;
	mat(int n) : n(n) {
		a.assign(n, vector<LL>(n, INF));
	}
	void make_unit() {
		for (int i = 0; i < n; ++i) a[i][i] = 0;
	}
	mat operator*(mat oth) const {
		mat ans(n);
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				for (int k = 0; k < n; ++k) {
					ans.a[i][j] = min(ans.a[i][j], a[i][k] + oth.a[k][j]);
				}
			}
		}
		return ans;
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int k; cin >> k;
	int n; cin >> n;
	int m; cin >> m;
	int o; cin >> o;
	int nn = (n + k - 1) / k;
	vector<vector<mat>> up(nn, vector<mat>(LOG, mat(k)));
	for (int i = 0, a, b, t; i < m; ++i) {
		cin >> a >> b >> t;
		up[a/k][0].a[a%k][b%k] = min(up[a/k][0].a[a%k][b%k], (LL)t);
	}
	for (int i = 1; i < LOG; ++i) {
		for (int j = 0; j < nn; ++j) {
			int oth = min(nn-1, j + (1 << (i-1)));
			up[j][i] = up[j][i-1]*up[oth][i-1];
		}
	}
	for (int i = 0, a, b; i < o; ++i) {
		cin >> a >> b;
		mat cur(k); cur.make_unit();
		int ka = a / k;
		int kb = b / k;
		int s = kb - ka;
		for (int j = LOG-1; j >= 0; --j) {
			if (s >= (1 << j)) {
				cur = cur * up[ka][j];
				ka += 1 << j;
				s -= 1 << j;
			}
		}
		int ans = cur.a[a%k][b%k];
		cout << (ans >= INF ? -1 : ans) << "\n";
	}
}

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