Submission #1045228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045228		Unforgettablepl	Toll (BOI17_toll)	C++17	100 / 100	228 ms	72204 KiB

toll

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

#define int long long

const int INF = 1e10;


int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int k,n,m,q;
	cin >> k >> n >> m >> q;
	auto combine = [&](vector<vector<int>> DPa,vector<vector<int>> DPb){
		vector DPres(k,vector(k,INF));
		for(int l=0;l<k;l++){
			for(int r=0;r<k;r++){
				for(int x=0;x<k;x++){
					DPres[l][r]=min(DPres[l][r],DPa[l][x]+DPb[x][r]);
				}
			}
		}
		return DPres;
	};
	int totBlocks = n/k;
	vector lift(totBlocks+1,vector(16,vector(k,vector(k,INF))));
	for(int i=1;i<=m;i++){
		int a,b,t;cin>>a>>b>>t;
		int block = a/k;
		a%=k;b%=k;
		lift[block][0][a][b]=t;
	}
	for(int bit=1;bit<16;bit++){
		for(int i=0;i<=totBlocks;i++){
			if(i+(1<<bit)>totBlocks)continue;
			lift[i][bit]=combine(lift[i][bit-1],lift[i+(1<<(bit-1))][bit-1]);
		}
	}
	for(int i=1;i<=q;i++){
		int a,b;cin>>a>>b;
		int blockA = a/k;a%=k;
		int blockB = b/k;b%=k;
		if(blockA==blockB){cout<<"-1\n";continue;}
		int tar = blockB-blockA;
		vector res(k,vector(k,INF));
		for(int j=0;j<k;j++)res[j][j]=0;
		for(int bit=0;bit<16;bit++)if(tar&(1<<bit)){
			res=combine(res,lift[blockA][bit]);
			blockA+=(1<<bit);
		}
		if(res[a][b]>=INF)cout<<"-1\n";
		else cout<<res[a][b]<<'\n';
	}
}

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