Submission #1115840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115840		kustizus	Toll (BOI17_toll)	C++17	100 / 100	161 ms	72408 KiB

toll

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

#define int long long
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define read_input(file) if (fopen(file".inp", "r")) freopen(file".inp", "r", stdin);
#define file(file) freopen (file".inp", "r", stdin); freopen (file".out", "w", stdout);

const int N = 5e4, inf = 1e12;
int n, m, o, k;

struct matrix{
	vector <vector<int>> d;
	void init(int n, int m, int v){
		d.resize(n, vector<int>(m, v));
	}
};

matrix operator* (const matrix &a, const matrix &b){
	matrix c;
	c.init(a.d.size(), b.d[0].size(), inf);
	for (int i = 0; i < (int)a.d.size(); ++i)
		for (int j = 0; j < (int)b.d[0].size(); ++j)
			for (int k = 0; k < (int)a.d[0].size(); ++k)
				c.d[i][j] = min(c.d[i][j], a.d[i][k] + b.d[k][j]);
	return c;
}

matrix M[N + 5];
matrix binlift[N + 5][17];

void solve(){
	cin >> k >> n >> m >> o;
	int sum = n / k;
	for (int i = 0; i <= sum; ++i)
		M[i].init(k, k, inf);
	for (int i = 1; i <= m; ++i){
		int u, v, w;
		cin >> u >> v >> w;
		M[u / k].d[u % k][v % k] = w;
	}
	for (int i = 0; i <= sum; ++i) binlift[i][0] = M[i];
	for (int i = 1; i <= 16; ++i)
		for (int j = 0; j <= sum - (1 << i); ++j)
			binlift[j][i] = binlift[j][i - 1] * binlift[j + (1 << (i - 1))][i - 1];
	while (o--){
		int u, v;
		cin >> u >> v;
		if (u > v){
			cout << "-1\n";
			continue;
		}
		matrix nw;
		nw.init(k, k, inf);
		nw.d[0][u % k] = 0;
		int s = u / k, t = v / k;
		for (int i = 16; i >= 0; --i)
			if (s + (1 << i) <= t){
				nw = nw * binlift[s][i];
				s += (1 << i);
			}
		cout << (nw.d[0][v % k] >= inf ? -1 : nw.d[0][v % k]) << "\n";
	}
}

signed main(){
    faster;
    // file("file");
    // read_input("file");
    int tt = 1;
    // cin >> tt;
    while (tt--){
        solve();
    }
}

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