Submission #788613

#	Time	Username	Problem	Language	Result	Execution time	Memory
788613		WLZ	Toll (BOI17_toll)	C++17	100 / 100	110 ms	16580 KiB

toll

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

typedef pair<int, int> ii;
const int INF = 1e9;
template<typename T> inline istream& operator>>(istream &i, vector<T>& v) {
	for (int j = 0; j < (int) v.size(); j++) i >> v[j];
	return i;
}
template<typename T> inline ostream& operator<<(ostream &o, const vector<T>& v) {
	for (int i = 0; i < (int) v.size(); i++) o << v[i] << ' ';
   	o << '\n';
	return o;	
}

struct node {
	vector<vector<int>> mat;
	node* left, *right;
	int i, j;
};

vector<vector<int>> combine(const vector<vector<int>>& mat1, const vector<vector<int>>& mat2) {
	if ((int) mat1.size() == 0) return mat2;
	if ((int) mat2.size() == 0) return mat1;
	int V = (int) mat1.size();
	vector<vector<int>> newMat(V, vector<int>(V, INF));
	for (int k = 0; k < V; k++) {
		for (int i = 0; i < V; i++) {
			for (int j = 0; j < V; j++) {
				newMat[i][j] = min(newMat[i][j], mat1[i][k] + mat2[k][j]);
			}	
		}
	}
	return move(newMat);
}

int k, n, m, o;
vector<vector<ii>> g;

node *build(int l, int r) {
	//cout << l << ' ' << r << '\n';
	if (l == r) {
		vector<vector<int>> newMat(k, vector<int>(k, INF));
		for (int i = l * k; i < (l + 1) * k; i++) {
			for (auto& v : g[i]) {
				newMat[i % k][v.first % k] = v.second;
			}
		}
		#ifdef DEBUG
		cout << l << ' ' << r << ' ' << newMat;
		#endif
		//cout << newMat;
		return new node{newMat, nullptr, nullptr, l, r};
	}
	int mid = (l + r) / 2;
	node *left = build(l, mid);
	node *right = build(mid + 1, r);
	//cout << left->mat << right->mat;
	vector<vector<int>> newMat = combine(left->mat, right->mat);
	#ifdef DEBUG
	cout << l << ' ' << r << ' ' << newMat;
	#endif
	return new node{newMat, left, right, l, r};	
}

vector<vector<int>> query(node *cur, int i, int j) {
	if (cur->i > j || cur->j < i) return vector<vector<int>>(0);
	if (cur->i >= i && cur->j <= j) return cur->mat;
	return combine(query(cur->left, i, j), query(cur->right, i, j));
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	cin >> k >> n >> m >> o;
	//cout << k << n << m << o;
	g.resize(n);
	for (int i = 0; i < m; i++) {
		int a, b, t;
		cin >> a >> b >> t;
		g[a].emplace_back(b, t);
	}
	//cout << (n - 1) / k - 1;
	node* root = build(0, (n - 1) / k - 1);	
	while (o--) {
		int s, t;
		cin >> s >> t;
		int sLayer = s / k;
		int tLayer = t / k - 1;
		if (sLayer > tLayer) {
			cout << "-1\n";
			continue;
		}
		vector<vector<int>> mat = query(root, sLayer, tLayer);
		//cout << mat;
		int ans = mat[s % k][t % k];
		if (ans >= INF) ans = -1;
		cout << ans << '\n';
	}
	return 0;
}

Compilation message (stderr)

toll.cpp: In function 'std::vector<std::vector<int> > combine(const std::vector<std::vector<int> >&, const std::vector<std::vector<int> >&)':
toll.cpp:34:13: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
   34 |  return move(newMat);
      |         ~~~~^~~~~~~~
toll.cpp:34:13: note: remove 'std::move' call

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