Submission #1274971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274971		muhammad-ahmad	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	358 ms	25960 KiB

Main

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

#define int long long
#define endl '\n'

const int N = 2e5 + 5;
int n, m, s, t, l, k, dists[N], distt[N], vis[N];
vector<pair<int, int>> adj[N];

signed main(){
    cin >> n >> m >> s >> t >> l >> k;
    for (int i = 1; i <= m; i++){
    	int u, v, w; cin >> u >> v >> w;
    	adj[u].push_back({v, w});
    	adj[v].push_back({u, w});
    }
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    
	q.push({0, s});
	for (int i = 1; i < N; i++) dists[i] = 1e18;
    dists[s] = 0;
	while (q.size()){
		auto [c, u] = q.top();
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (auto [v, w] : adj[u]){
			if (dists[u] + w < dists[v]){
				dists[v] = dists[u] + w;
				q.push({dists[v], v});
			}
		}
	}
	
    for (int i = 1; i < N; i++) {vis[i] = 0;}
    
    q.push({0, t});
	for (int i = 1; i < N; i++) distt[i] = 1e18;
    distt[t] = 0;
	while (q.size()){
		auto [c, u] = q.top();
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (auto [v, w] : adj[u]){
			if (distt[u] + w < distt[v]){
				distt[v] = distt[u] + w;
				q.push({distt[v], v});
			}
		}
	}
    
    vector<int> bs;
    for (int i = 1; i <= n; i++) bs.push_back(distt[i]);
    sort(bs.begin(), bs.end());
    
    if (dists[t] <= k){
    	cout << (n * (n - 1)) / 2 << endl;
    	return 0;
    }
    
    int ans = 0;
    
    for (int i = 1; i <= n; i++){
    	int left = k - (dists[i] + l);
    	int le = -1, r = bs.size();
    	while (r - le > 1){
    		int mid = (r + le) / 2;
    		if (bs[mid] <= left) le = mid;
    		else r = mid;
    	} 
    	ans += le + 1;
    }
//     
    cout << ans << endl;
    
	return 0;
}

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