Submission #1115816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115816		vjudge1	Railway (BOI17_railway)	C++17	0 / 100	325 ms	524288 KiB

railway

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9 + 7;

struct matrix {
	vector<vector<int>> data;
	
	matrix() {}
	matrix(int n, int m) : data(n, vector<int>(m)) {}
	matrix(vector<vector<int>>& v) : data(v) {}
	
	int row() const {return data.size();}
	int col() const {return data[0].size();}
	auto & operator [] (int i) {return data[i];}
	const auto & operator [] (int i) const {return data[i];}
	
	friend matrix operator * (const matrix& a, const matrix& b) {
		matrix res(a.row(), b.col());
		for (int i = 0; i < a.row(); ++i)
			for (int j = 0; j < b.col(); ++j) {
				res[i][j] = inf;
				for (int k = 0; k < b.row(); ++k)
					res[i][j] = min(res[i][j], a[i][k] + b[k][j]);
			}
		return res;
	}	
	
	friend ostream& operator << (ostream& out, const matrix& o) {
		for (auto r : o.data) {
			for (int i : r) out << i << ' ';
			out << '\n';
		}
		out << '\n';
		return out;
	}
};

vector<pair<int, int>> radj[50008];
matrix trans[50008][16];


void build_binlift(int n) {
	for (int lg = 1; (1 << lg) <= n; ++lg) for (int i = 0; i + (1 << lg) - 1 < n; ++i)
		trans[i][lg] = trans[i][lg - 1] * trans[i + (1 << (lg - 1))][lg - 1];
}

matrix identity_matrix(int n) {
	matrix I(n, n);
	for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) I[i][j] = (i == j ? 0 : inf);
	return I;
}

int k;
matrix res; int pt, dist;
matrix query(int l, int r) {
	res = identity_matrix(k); pt = l; dist = r - l + 1;
	for (int bit = 0; bit < 16; ++bit) if (dist & (1 << bit)) {
		res = res * trans[pt][bit];
		pt += (1 << bit);
	}
	return res;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m, q, u, v, w; cin >> k >> n >> m >> q; 
	if (n % k) n = n - n % k + k;
	while (m--) cin >> u >> v >> w, radj[v].push_back({u, w});
	for (int b = 0; b < n / k; ++b) {
		trans[b][0] = matrix(k, k);
		for (int i = 0; i < k; ++i) {
			for (int j = 0; j < k; ++j) trans[b][0][j][i] = inf;
			for (pair<int, int> r_edge : radj[b * k + i]) trans[b][0][r_edge.first % k][i] = r_edge.second;
		}
	}
	build_binlift(n / k); matrix T, dp;
	while (q--) {
		cin >> u >> v;
		if (u == v) cout << 0 << '\n';
		else if (u / k + 1 > v / k) cout << -1 << '\n';
		else {
			T = query(u / k + 1, v / k);
			dp = matrix(1, k);
			for (int i = u - u % k; i < u - u % k + k; ++i) dp[0][i % k] = (i == u ? 0 : inf);
			dp = dp * T;
			cout << (dp[0][v % k] == inf ? -1 : dp[0][v % k]) << '\n';
		}
	}
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25