Submission #1283125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283125		Jawad_Akbar_JJ	Toll (BOI17_toll)	C++20	0 / 100	152 ms	98316 KiB

toll

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 50005, inf = 2e9;

struct mat{
	int dst[5][5];

	mat(){
		for (int i=0;i<5;i++)
			for (int j=0;j<5;j++)
				dst[i][j] = inf;
	}

	mat operator *(mat Nw){
		mat res;
		for (int k=0;k<5;k++){
			for (int i=0;i<5;i++)
				for (int j=0;j<5;j++)
					res.dst[i][j] = min(res.dst[i][j], dst[i][k] + Nw.dst[k][j]);
		}
		return res;
	}
} Mn[N][20];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	int k, n, m, o;
	cin>>k>>n>>m>>o;

	for (int i=1, a, b, c;i<=m;i++){
		cin>>a>>b>>c;
		Mn[a / k][0].dst[a % k][b % k] = c;
	}

	n /= k;
	for (int i=n;i>=0;i--){
		for (int j=0;i + (1<<j) <= n;j++)
			Mn[i][j+1] = Mn[i][j] * Mn[i + (1<<j)][j];
	}

	for (int i=1, a, b;i<=o;i++){
		cin>>a>>b;
		if (b / k <= a / k){
			cout<<-1<<'\n';
			return 0;
		}
		int d = b / k - a / k - 1, cur = a / k + 1;
		mat Now = Mn[a / k][0];
		for (int i=0;i<17;i++){
			if ((1<<i) & d)
				Now = Now * Mn[cur][i], cur += (1<<i);
		}
		if (Now.dst[a % k][b % k] == 1e9)
			cout<<-1<<'\n';
		else
			cout<<Now.dst[a % k][b % k]<<'\n';
	}
}

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