Submission #1111047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111047		Alihan_8	Toll (BOI17_toll)	C++17	0 / 100	129 ms	61620 KiB

toll

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ar array

const int inf = 1e9;

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int k, n, m, q;
	cin >> k >> n >> m >> q;
	
	vector <vector<ar<int,2>>> adj(n), rev(n);
	
	for ( int i = 0; i < m; i++ ){
		int u, v, w; cin >> u >> v >> w;
		
		adj[u].pb({v, w});
		rev[v].pb({u, w});
	}
	
	vector <vector<int>> qu(n / k + 1);
	
	for ( int i = 0; i < n; i++ ) qu[i / k].pb(i);
	
	auto calc = [&](int sx, int l, int r, auto &adj){
		vector <int> dp(r - l + 1, inf);
		
		dp[sx - l] = 0;
		
		priority_queue <ar<int,2>> q;
		
		q.push({0, sx});
		
		while ( !q.empty() ){
			auto [val, u] = q.top();
			q.pop(); val *= -1;
			
			if ( val != dp[u - l] ) continue;
			
			for ( auto &[v, w]: adj[u] ){
				if ( v < l || v > r ) continue;
				
				if ( dp[v - l] > val + w ){
					dp[v - l] = val + w;
					q.push({-dp[v - l], v});
				}
			}
		}
		
		return dp;
	};
	
	vector <vector<vector<int>>> lf(20, vector <vector<int>> (n)), rg(20, vector <vector<int>> (n));
	
	auto dnc = [&](auto dnc, int l, int r, int lvl) -> void{
		if ( l > r ) return;
		
		int m = (l + r) / 2;
		
		for ( auto &u: qu[m] ){
			lf[lvl][u] = calc(u, l * k, m * k + k - 1, rev);
			rg[lvl][u] = calc(u, m * k, r * k + k - 1, adj);
		}
		
		dnc(dnc, l, m - 1, lvl + 1);
		dnc(dnc, m + 1, r, lvl + 1);
	};
	
	dnc(dnc, 0, (n - 1) / k, 0);
	
	auto qry = [&](int u, int v){
		if ( u / k == v / k ) return -1;
		
		int l = 0, r = (n - 1) / k, lvl = 0;
		
		while ( true ){
			int m = (l + r) / 2;
			
			int opt = inf, found = 0;
			
			for ( auto &t: qu[m] ){
				if ( l * k <= t && (r + 1) *k > t ){
					opt = min(opt, lf[lvl][t][u - l * k] + rg[lvl][t][v - m * k]);
					
					found = 1;
				}
			}
			
			if ( found ){
				if ( opt == inf ) opt = -1;
				
				return opt;
			}
			
			if ( m * k > v ) r = m - 1;
			else l = m + 1;
			
			lvl += 1;
		}
	};
	
	while ( q-- ){
		int u, v; cin >> u >> v;
		
		cout << qry(u, v);
		
		if ( q > 0 ) cout << '\n';
	}
}

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