Submission #1262037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262037		nlsosad	Toll (BOI17_toll)	C++20	100 / 100	143 ms	37604 KiB

toll

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int, int>> a[50001];
int bin[50001][16][5];
int inf = 1e18;
int n, k, m, q;
vector<bool> vst(50001, false);
void dfs(int i){
	stack<int> st;
	st.push(i);
	while(!st.empty()){
		int u = st.top();
		st.pop();
		vst[u] = true;
		for (auto [v, w]:a[u]){
			if(!vst[v]){
				st.push(v);
			}
			bin[u][0][v%k] = w;
		}
	}
}
int query(int u, int v){
	if(u/k >= v/k or !vst[u] or !vst[v])return -1;
	int dif = v/k - u/k;
	vector<int> sol(k, 0);
	bool check = false;
	int lev = u/k;
	for (int bit = 15;bit>=0;--bit){
		if(dif & (1<<bit)){
			if(!check){
				for (int p = 0;p<k;++p){
					sol[p] = bin[u][bit][p];
				}
				check = true;
			}else{
				vector<int> tmp(k, inf);
				for (int p = 0;p<k;++p){
					for (int q = 0;q<k;++q){
						tmp[p] = min(tmp[p], sol[q] + bin[lev*k + q][bit][p]);
					}
				}
				for (int p = 0;p<k;++p){
					sol[p] = tmp[p];
				}
			}
			// cout << '\n';
			lev += (1<<bit);
		}
	}
	return sol[v%k];
}

signed main(){
	cin >> k >> n >> m >> q;
	for (int i = 1;i<=m;++i){
		int u, v, w;
		cin >> u >> v >> w;
		a[u].push_back({v, w});
	}
	for (int i = 0;i<n;++i){
		vst[i] = false;
		for (int j = 0;j<16;++j){
			for (int p = 0;p<k;++p){
				bin[i][j][p] = inf;
			}
		}
	}
	for (int i = 0;i<n;++i){
		if(!vst[i] and !a[i].empty())dfs(i);
	}
	for(int j = 1;j<16;++j){
		for (int i = 0;i<n;++i){
			if(!vst[i])continue;
			for (int p = 0;p<k;++p){
				bin[i][j][p] = inf;
				int lev = i/k;
				for (int q = 0;q<k;++q){
					if((lev + (1<<(j-1)))*k+q>=n)continue;
					bin[i][j][p] = min(bin[i][j][p], bin[i][j-1][q] + bin[ (lev + (1<<(j-1)))*k+q][j-1][p]);
				}
			}
		}
	}
	while(q--){
		int u, v;
		cin >> u >> v;
		int t = query(u, v);
		if(t==inf)t = -1;
		cout << t << '\n';
	}
}

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