Submission #472596

#	Time	Username	Problem	Language	Result	Execution time	Memory
472596		disastah	Toll (BOI17_toll)	C++17	7 / 100	92 ms	39296 KiB

toll

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ar array
using namespace std;
typedef long double ld;
typedef long long ll;
const int inf=1e9+9;
const ll linf=4e18+18;
const int N=5e4;

int k, n, m, q;
vector<ar<int,2>> g[N], rg[N];
ll dst[20][N][5]; int dst_mask[N];

void build_dst(int h, int l, int r) {
	assert(l<r);
	int m=(l+r)/2;
	for (int i=m*k; i<r*k; ++i) dst_mask[i]^=(1<<h);
	for (int k0=0; k0<k; ++k0) {
		dst[h][m*k+k0][k0]=0;
		for (int i=m*k+k0-1; i>=l*k; --i) {
			dst[h][i][k0]=inf;
			for (auto &[u,t] : g[i]) {
				if (u>m*k+k0) continue;
				dst[h][i][k0]=min(dst[h][i][k0],dst[h][u][k0]+t);
			}
		}
		for (int i=m*k+k0+1; i<r*k; ++i) {
			dst[h][i][k0]=inf;
			for (auto &[u,t] : rg[i]) {
				if (u<m*k+k0) continue;
				dst[h][i][k0]=min(dst[h][i][k0],dst[h][u][k0]+t);
			}
		}
	}
	if (l+1<r) {
		build_dst(h+1,l,m);
		build_dst(h+1,m,r);
	}
}

void solve() {
	cin >> k >> n >> m >> q;
	for (int i=0; i<m; ++i) {
		int a, b, t; cin >> a >> b >> t;
		g[a].push_back({b,t});
		rg[b].push_back({a,t});
	}
	build_dst(0,0,(n+k-1)/k);
	while(q--) {
		int a, b; cin >> a >> b;
		int h=__builtin_ctz(dst_mask[a]^dst_mask[b]);
		assert(h<30);
		ll ans=inf;
		for (int i=0; i<k; ++i) ans=min(ans,dst[h][a][i]+dst[h][b][i]);
		cout << (ans<inf?ans:-1) << "\n";
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
#ifdef disastah
	cout << "Output\n\n";
#endif
	int tt=1;
//	cin >> tt;
	while (tt--) {
		solve();
		cout << "\n";
	}
}

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