Submission #1214208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214208		trimkus	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	217 ms	26472 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	int s, t, l;
	ll k;
	cin >> s >> t >> l >> k;
	vector<vector<pair<int, int>>> adj(n + 1);
	for (int i = 0; i < m; ++i) {
		int a, b, w;
		cin >> a >> b >> w;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
	}
	auto dijikstra = [&](int st, vector<ll>& dist) -> void {
		priority_queue<array<ll, 2>> pq;
		pq.push({0, st});
		dist[st] = 0;
		while (pq.size()) {
			ll d = -pq.top()[0];
			int v = pq.top()[1];
			pq.pop();
			if (dist[v] != d) continue;
			for (auto& [u, w] : adj[v]) {
				if (dist[u] > dist[v] + w) {
					dist[u] = dist[v] + w;
					pq.push({-dist[u], u});
				}
			}
		}
	};
	const ll INF = 1e18;
	vector<ll> dist1(n + 1, INF), dist2(n + 1, INF);
	dijikstra(s, dist1);
	dijikstra(t, dist2);
	ll res = 0;
	if (dist1[t] <= k) {
		cout << 1LL * n * (n - 1) / 2 << "\n";
		return 0;
	}
	vector<array<ll, 2>> tot_dist1, tot_dist2;
	for (int i = 1; i <= n; ++i) {
		tot_dist2.push_back({dist2[i], i});
	}
	for (int i = 1; i <= n; ++i) {
		tot_dist1.push_back({dist1[i], i});
	}
	sort(begin(tot_dist1), end(tot_dist1));
	sort(begin(tot_dist2), end(tot_dist2));
	int ptr = (int)tot_dist2.size() - 1;
	vector<int> in(n + 1);
	for (auto& [_, i] : tot_dist2) in[i] = 1;
	for (int i = 0; i < (int)tot_dist1.size(); ++i) {
		ll total = tot_dist1[i][0] + l;
		while (ptr >= 0) {
			ll now = min(total, dist1[tot_dist2[ptr][1]]) + tot_dist2[ptr][0];
			if (now > k) {
				in[tot_dist2[ptr][1]] = 0;
				ptr -= 1;
			} else {
				break;
			}
		}
		res += ptr + 1 - in[tot_dist1[i][1]];
	}
	cout << res << "\n";
}

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 29 / 29
• Subtask 4: 47 / 47