제출 #1261998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261998		nlsosad	Toll (BOI17_toll)	C++20	0 / 100	83 ms	32832 KiB

toll

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int, int>> a[50001];
int bin[50001][14][5];
int inf = 1e18;
int n, k, m, q;
vector<bool> vst(50001, false);
void dfs(int u){
	vst[u] = true;
	for (auto [v, w]:a[u]){
		bin[u][0][v%k] = w;
		if(!vst[v]){
			dfs(v);
		}
	}
}

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 = 13;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];
				}
			}
			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});
	}
	// cout << vst[13];return 0;
	for (int i = 0;i<n;++i){
		vst[i] = false;
		for (int j = 0;j<14;++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);
	}
	// cout << vst[13];return 0;
	for(int j = 1;j<14;++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(i==0 and q==2 and p==2){
						cout <<  (lev + (1<<(j-1)))*k+q << " LON\n";
						cout << bin[i][j-1][q] << " BUOI\n";
						cout << bin[ (lev + (1<<(j-1)))*k+q][j-1][p] << " SV\n";
						cout << bin[i][j-1][q] + bin[ (lev + (1<<(j-1)))*k+q][j-1][p] << " NGU\n";
						// return 0;
					}*/
					if(i==0 and j==1 and p==2){
						// cout << i << ' ' << j << ' ' << p << ' ' << q << '\n';
						// cout << bin[i][j-1][q] << ' ' << bin[ (lev + (1<<(j-1)))*k+q][j-1][p] << '\n';
					}
					bin[i][j][p] = min(bin[i][j][p], bin[i][j-1][q] + bin[ (lev + (1<<(j-1)))*k+q][j-1][p]);
				}
			}
		}
	}
	// cout << bin[0][1][2];return 0;
	while(q--){
		int u, v;
		cin >> u >> v;
		cout << query(u, v) << '\n';
	}
}

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