Submission #223745

#	Time	Username	Problem	Language	Result	Execution time	Memory
223745		johutha	Toll (BOI17_toll)	C++17	100 / 100	265 ms	23800 KiB

toll

#include <iostream>
#include <vector>
#include <algorithm>

#define int int64_t

using namespace std;

int k;
struct block
{
	vector<vector<int>> bl;

	block() : bl(vector<vector<int>>(k, vector<int>(k, 1e11))) {}

	static block nt()
	{
		block b;
		for (int i = 0; i < k; i++) b.bl[i][i] = 0;
		return b;
	}

	static block merge(const block& b1, const block& b2)
	{
		block res;
		for (int i = 0; i < k; i++)
		{
			for (int j = 0; j < k; j++)
			{
				for (int l = 0; l < k; l++)
				{
					res.bl[i][j] = min(res.bl[i][j], b1.bl[i][l] + b2.bl[l][j]);
				}
			}
		}
		return res;
	}

	void print()
	{
		return;
		for (int i = 0; i < k; i++)
		{
			for (int j = 0; j < k; j++)
			{
				cout << bl[i][j] << " ";
			}
			cout << "\n";
		}
		cout << "\n";
	}
};

struct segtree
{
	vector<block> table;

	block query(int ql, int qr, int l, int r, int pos)
	{
		if (ql <= l && r <= qr) return table[pos];
		if (qr < l || r < ql) return block::nt();
		return block::merge(query(ql, qr, l, (l + r)/2, 2*pos + 1), query(ql, qr, (l + r)/2 + 1, r, 2*pos + 2));
	}

	void build(const vector<block>& vals, int l, int r, int pos)
	{
		if (l == r)
		{
			table[pos] = vals[l];
			return;
		}
		build(vals, l, (l + r)/2, 2*pos + 1);
		build(vals, (l + r)/2 + 1, r, 2*pos + 2);
		table[pos] = block::merge(table[2*pos + 1], table[2*pos + 2]);
	}
};

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, m, o;
	cin >> k >> n >> m >> o;
	n += k - (k % n);
	int nbl = (n / k);
	vector<block> bls(nbl);

	for (int i = 0; i < m; i++)
	{
		int a, b, w;
		cin >> a >> b >> w;
		int cb = a / k;
		a %= k;
		b %= k;
		bls[cb].bl[a][b] = min(bls[cb].bl[a][b], w);
	}

	segtree st;
	st.table.resize(4*nbl);
	st.build(bls, 0, nbl - 1, 0);

	for (auto bl : bls)
	{
		bl.print();
	}
	
	for (int i = 0; i < o; i++)
	{
		int fr, to;
		cin >> fr >> to;
		if ((fr / k) == (to / k))
		{
			cout << "-1\n";
			continue;
		}
		auto bl = st.query((fr / k), (to / k) - 1, 0, nbl - 1, 0);
		bl.print();
		int v = bl.bl[fr % k][to % k];
		cout << (v >= 1e11 ? -1 : v) << "\n";
	}
}

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