Submission #298035

#	Time	Username	Problem	Language	Result	Execution time	Memory
298035		miss_robot	Toll (BOI17_toll)	C++14	100 / 100	264 ms	73596 KiB

toll

#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#define int long long

using namespace std;

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	int k, n, m, o, L = 16, INF = numeric_limits<int>::max()/8;
	cin >> k >> n >> m >> o;
	vector< vector< vector< vector<int> > > > g(L, vector< vector< vector<int> > >((n+k-1)/k, vector< vector<int> >(k, vector<int>(k, INF))));
	while(m--){
		int a, b, t;
		cin >> a >> b >> t;
		g[0][a/k][a%k][b%k] = t;
	}
	for(int i = 1; i < L; i++)
		for(int j = 0; j < (n+k-1)/k-(1<<i); j++)
			for(int u = 0; u < k; u++)
				for(int v = 0; v < k; v++)
					for(int w = 0; w < k; w++)
				g[i][j][u][v] = min(g[i][j][u][v], g[i-1][j][u][w]+g[i-1][j+(1<<(i-1))][w][v]);
	while(o--){
		int a, b, pos;
		cin >> a >> b;
		if(a/k == b/k){
			cout << "-1\n";
			continue;
		}
		vector<int> dis(k, INF);
		dis[a%k] = 0;
		pos = a/k;
		for(int i = L-1; i >= 0; i--){
			if(pos + (1<<i) > b/k) continue;
			vector<int> newdis(k, INF);
			for(int u = 0; u < k; u++)
				for(int v = 0; v < k; v++)
					newdis[v] = min(newdis[v], dis[u]+g[i][pos][u][v]);
			dis = newdis;
			pos += (1<<i);
		}
		cout << (dis[b%k]==INF?-1:dis[b%k]) << "\n";
	}
}

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