Submission #1160944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160944		Pwo	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	208 ms	25864 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, m, s, t, l, k;
vector<pair<int, int>> g[200005];
int ds[200005], dt[200005];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> d, e;

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> s >> t >> l >> k;
	for (int i = 0; i < m; i++) {
		int u, v, w; cin >> u >> v >> w;
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
	}
	
	fill(ds, ds + n + 1, 1e18);
	fill(dt, dt + n + 1, 1e18);
	
	ds[s] = 0;
	pq.emplace(0, s);
	while (!pq.empty()) {
		auto c = pq.top(); pq.pop();
		if (ds[c.second] != c.first) continue;
		for (auto u : g[c.second]) {
		if (ds[u.first] > c.first + u.second) {
				ds[u.first] = c.first + u.second;
				pq.emplace(ds[u.first], u.first);
			}
		}
	}
	
	dt[t] = 0;
	pq.emplace(0, t);
	while (!pq.empty()) {
		auto c = pq.top(); pq.pop();
		if (dt[c.second] != c.first) continue;
		for (auto u : g[c.second]) {
		if (dt[u.first] > c.first + u.second) {
				dt[u.first] = c.first + u.second;
				pq.emplace(dt[u.first], u.first);
			}
		}
	}

	if (ds[t] <= k) { cout << (n * (n - 1)) / 2; return 0;}
	
	int ans = 0;
	for (int i = 1; i <= n; i++) d.push_back(dt[i]);
	for (int i = 1; i <= n; i++) e.push_back(ds[i]);
	sort(d.begin(), d.end());
	sort(e.begin(), e.end());
	
	for (int i = 1; i <= n; i++) {
		int c = k - l - ds[i];
		int it = upper_bound(d.begin(), d.end(), c) - d.begin();
		ans += it;
		int it2 = upper_bound(e.begin(), e.end(), k - l - dt[i]) - e.begin();
		ans += it2;
	}
	
	cout << ans / 2;
}

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