Submission #328885

#	Time	Username	Problem	Language	Result	Execution time	Memory
328885		Cantfindme	Toll (BOI17_toll)	C++17	100 / 100	145 ms	177644 KiB

toll

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
typedef pair<int,pi> pii;

const int maxn = 50010;
const int INF = INT_MAX/2;

//2^16
int dist[maxn][18][5][5];
int k, n, e, q;

int32_t main() {
	FAST
	cin >> k >> n >> e >> q;
	
	for (int i =0;i<=n/k;i++) {
		for (int j = 0; j <17;j++) {
			for (int x = 0; x < k;x++) {
				for (int y=0; y < k; y++) {
					dist[i][j][x][y] = INF;
				}
			}
		}
	}
	
	for (int i =0;i<e;i++) {
		int a,b,c; cin >> a >> b >> c;
		dist[a/k][0][a % k][b % k] = c;
	}
	
	for (int b = 1; b < 17; b++) {
		for (int i =0; i <= n; i++) {
			if (i*k + (1 << b)*k > n) continue;
			
			for (int mid = 0; mid < k; mid++) {
				for (int x = 0; x < k; x++) {
					for (int y = 0; y < k; y++) {
						int newi = i + (1 << (b-1));
						int newd = dist[i][b-1][x][mid] + dist[newi][b-1][mid][y];
						dist[i][b][x][y] = min(dist[i][b][x][y], newd) ;
					}
				}
			}
			
		}
	}
	
	int bestprev[5];
	int best[5];
	for (int qq = 0; qq < q; qq++) {
		int a, b; cin >> a >> b;
		
		int curbuc = a/k;
		int finalbuc = b/k;
		memset(best,0,sizeof best);
	
		for (int x=0;x<k;x++) bestprev[x] = INF;
		bestprev[a%k] = 0;
		
		for (int k2 = 16; k2 >= 0; k2--) {
			if (curbuc + (1 << k2) > finalbuc) continue;
			
			for (int y = 0; y < k; y++) {
				best[y] = INF;
				for (int x = 0; x< k;x++) {
					best[y] = min(best[y], bestprev[x] + dist[curbuc][k2][x][y]);
				}
			}
			swap(bestprev,best);
			curbuc += (1 << k2);
		}

		int ans = bestprev[b%k];
		if (ans >= INF) cout << "-1\n";
		else cout << ans << "\n";
	}
	
}

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