Submission #1326661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326661		sonarcht	Toll (BOI17_toll)	C++20	100 / 100	308 ms	13068 KiB

toll

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(v) begin(v), end(v)
#define pll pair<ll, ll>
#define fi first
#define se second
#define vll vector<ll>
#define mll map<ll, ll>
mt19937_64 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
const ll N = 1e5 + 6, inf = 1e18 + 7, mod = 1e9 + 7;
ll n, m, k, q, ans[N], a[N], b[N], dist[N];
pll qry[N];
vll v;
vector<pll> adj[N], adj2[N];
priority_queue<pll, vector<pll>, greater<pll>> pq;

void dijkstra(ll s, ll l, ll r) {
	for (int i = l*k; i < min(n, r*k + k); ++i) dist[i] = inf;
	dist[s] = 0;
	pq.push({0, s});
	while (!pq.empty()) {
		auto [d, u] = pq.top();
		pq.pop();
		if (d != dist[u]) continue;
		for (auto [v, w] : adj[u]) {
			if (l <= b[v] && b[v] <= r && d + w < dist[v]) {
				dist[v] = d + w;
				pq.push({d+w, v});
			}
		}
	}
	pq.push({0, s});
	while (!pq.empty()) {
		auto [d, u] = pq.top();
		pq.pop();
		if (d != dist[u]) continue;
		for (auto [v, w] : adj2[u]) {
			if (l <= b[v] && b[v] <= r && d + w < dist[v]) {
				dist[v] = d + w;
				pq.push({d+w, v});
			}
		}
	}
}

void dnc(ll l, ll r, vll v) {
	//cout << "L R " << l << " " << r << endl;
	if (v.empty()) return;
	ll mid = (l+r) / 2;
	//cout << "mid " << mid << endl;
	for (int i = mid*k; i < min(n, mid*k + k); ++i) {
		//cout << "i " << i << endl;
		dijkstra(i, l, r);
		// for (int j = l*k; j < min(n, r*k + k); ++j) 
			// cout << j << " " << (dist[j] == inf ? -1 : dist[j]) << endl; cout << endl;
		for (auto j : v) {
			auto [x, y] = qry[j];
			if (b[x] <= mid && mid < b[y]) ans[j] = min(ans[j], dist[x] + dist[y]); 
		}
	}
	vll vl, vr;
	for (auto i : v) {
		//cout << l << " " << r << " " << i << " " << ans[i] << endl;
		auto [x, y] = qry[i];
		if (b[y] <= mid) vl.pb(i);
		if (b[x] > mid) vr.pb(i);
	}
	dnc(l, mid, vl);
	dnc(mid+1, r, vr);
}

void solve() {
	cin >> k >> n >> m >> q;
	for (int i = 0; i < n; ++i) b[i] = i / k;
	for (int i = 1; i <= m; ++i) {
		ll x, y, w;
		cin >> x >> y >> w;
		adj[x].pb({y, w});
		adj2[y].pb({x, w});
	}
	for (int i = 1; i <= q; ++i) {
		ans[i] = inf;
		cin >> qry[i].fi >> qry[i].se;
		if (b[qry[i].fi] == b[qry[i].se]) ans[i] = -1;
		else v.pb(i);
	}
	dnc(0, n-1, v);
	for (int i = 1; i <= q; ++i) cout << (ans[i] == inf ? -1 : ans[i]) << endl;
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	if (fopen(".INP", "r")) {
		freopen(".INP", "r", stdin);
		freopen(".OUT", "w", stdout);
	}
	ll tc = 1;
//	cin >> tc;
	while (tc--) {
		solve();
	}
	return 0;
}

	

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:101:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |                 freopen(".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~
toll.cpp:102:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |                 freopen(".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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