Submission #702476

#	Time	Username	Problem	Language	Result	Execution time	Memory
702476		RandomLB	Toll (BOI17_toll)	C++17	7 / 100	739 ms	524288 KiB

toll

#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
#define F first
#define S second
#define pb push_back
#define siz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ms(x, a) memset(x, a, sizeof(x))
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values){
	string delim = "";
	cout << vars << " = ";
	(...,(cout << delim << values, delim = ", "));
	cout << endl;
}
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
//=================================
const int MAX = 5e4+5;
vector<pi> adj[MAX], radj[MAX];
int tl[MAX], tr[MAX], res[MAX], dis[5][MAX], k;
bool vis[MAX];

void solve(int l, int r, vector<int> vec){
	if (l/k == r/k) return;
	int m = l+(r-l)/2/k;
	//deb(l, r, m);
	for (int i = 0; i < k; i++){
		for (int j = l; j <= r; j++){
			dis[i][j] = INF;
			vis[j] = false;
		}
		queue<int> q;
		q.push(m*k+i); dis[i][m*k+i] = 0;
		while (siz(q)){
			int v = q.front(); q.pop();
			for (auto[u, w]: radj[v]){
				if (u < l) continue;
				dis[i][u] = min(dis[i][u], dis[i][v]+w);
				if (!vis[u]){ vis[u] = true; q.push(u); }
			}
		}
		q.push((m+1)*k+i); dis[i][(m+1)*k+i] = 0;
		while (siz(q)){
			int v = q.front(); q.pop();
			for (auto[u, w]: adj[v]){
				if (u > r) continue;
				dis[i][u] = min(dis[i][u], dis[i][v]+w);
				if (!vis[u]){ vis[u] = true; q.push(u); }
			}
		}
	}
	//deb(dis[2][0], dis[2][12]);
	vector<int> v1, v2;
	for (int i: vec){
		//deb(i, tl[i], tr[i]);
		if (tl[i]/k <= m && tr[i]/k > m){
			for (int a = 0; a < k; a++){
				for (auto[b, w]: adj[m*k+a]){
					res[i] = min(res[i], dis[a][tl[i]]+w+dis[b-(m+1)*k][tr[i]]);
				}
			}
		} else if (tr[i]/k <= m) v1.pb(i); else v2.pb(i);
	}
	solve(l, (m+1)*k-1, v1); solve((m+1)*k, r, v2);
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, m, q; cin >> k >> n >> m >> q;
	for (int i = 1; i <= m; i++){
		int a, b, w; cin >> a >> b >> w;
		adj[a].pb({b, w});
		radj[b].pb({a, w});
	}
	vector<int> v;
	for (int i = 1; i <= q; i++){
		cin >> tl[i] >> tr[i];
		v.pb(i);
	}
	ms(res, INF);
	solve(0, n/k*k+k-1, v);
	for (int i = 1; i <= q; i++) cout << (res[i] < INF? res[i] : -1) << "\n";
}

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