Submission #1184206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184206		Onur_Ilgaz	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	138 ms	25128 KiB

Main

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;

int32_t main() {
	fast
	int n, m;
	cin >> n >> m;
	int s, t, l, k;
	cin >> s >> t >> l >> k;
	s--, t--;
	vector <vector<pair<int, int> > > adj(n);
	for(int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		a--, b--;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
	}
	auto dij = [&](int st) {
		vector <int> dist(n, inf);
		vector <bool> vis(n);
		priority_queue <pair<int, int> > pq;
		pq.push({0, st});
		dist[st] = 0;
		while(!pq.empty()) {
			auto [d, node] = pq.top();
			d = -d;
			pq.pop();
			if(vis[node]) continue;
			vis[node] = 1;
			for(auto [to, w]:adj[node]) {
				if(d + w < dist[to]) {
					dist[to] = d + w;
					pq.push({-(d + w), to});
				}
			}
		}
		return dist;
	};
	vector <int> from = dij(s), to = dij(t);
	// for(auto it:from) {
	// 	cout << it << ' ';
	// }
	// cout << '\n';
	// for(auto it:to) {
	// 	cout << it << ' ';
	// }
	// cout << '\n';
	if(from[t] <= k) {
		cout << n * (n - 1) / 2 << '\n';
		return 0;
	}
	int ans = 0;
	sort(from.begin(), from.end());
	sort(to.begin(), to.end());
	k -= l;
	for(int i = 0; i < n; i++) {
		int v = k - from[i];
		ans += upper_bound(to.begin(), to.end(), v) - to.begin();
	}
	cout << ans << '\n';
}

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