Submission #1184986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184986		lalig777	Toll (BOI17_toll)	C++20	100 / 100	241 ms	73312 KiB

toll

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<vvvll> vvvvll;

int K, N, M, O;
int levs;
vvvvll dp;


ll func(int levi, int i, int k, int j, int l){
	if (levi+(1<<k)>=levs) return 1e18;
	return dp[levi][i][k][l]+dp[levi+(1<<k)][l][k][j];
}

void ini(){
	for (int k=1; k<20; k++){
		for (int levi=0; levi<levs-1; levi++){
			for (int i=0; i<K; i++){
				for (int j=0; j<K; j++){
					for (int l=0; l<K; l++){
						dp[levi][i][k][j]=min(dp[levi][i][k][j], func(levi,i,k-1,j,l));
					}
				}
			}
		}
	}return;
}

ll binlift(int a, int b){
	int act=a/K, fin=b/K;
	if(act==fin){
	  if (a==b) return 0;
	  else return -1;
	}
	vector<ll>res(K, 1e18);
	res[a%K]=0;
	for (int k=19; k>=0; k--){
		if (act+(1<<k)<fin){
			vector<ll>aux(K, 1e18);
			for (int i=0; i<K; i++){
				for (int j=0; j<K; j++) aux[i]=min(aux[i], res[j]+dp[act][j][k][i]);
			}swap(res, aux);
			act=act+(1<<k);
		}
	}
	ll ans=1e18;
	for (int i=0; i<K; i++) ans=min(ans, res[i]+dp[act][i][0][b%K]);
	if (ans==1e18) return -1;
	else return ans;
}

int main(){
	cin>>K>>N>>M>>O;
	levs=ceil(N/K);
	dp.assign(levs, vvvll(K, vvll(20, vll(K, 1e18))));
	for (int i=0; i<M; i++){
		int a, b; ll t;
		cin>>a>>b>>t;
		dp[a/K][a%K][0][b%K]=t;
	}
	ini();
	while (O--){
		int a, b;
		cin>>a>>b;
		cout<<binlift(a, b)<<'\n';
	}
	return 0;
}

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