Submission #1158575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158575		akacool445k	Construction Project 2 (JOI24_ho_t2)	C++20	0 / 100	1 ms	396 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
#define pint pair<int, int>
#define vint vector<pair<int, int>>
const int mod = 1e9 + 7;
const int shrek = 5e5 + 5;
const int say = INT_MAX / 2;
const int gex = INT_MIN / 2;
const long long oo = 1e18;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
	cout.tie(0);
	int n, m; cin >> n >> m;
	int s, t, l, k;
	cin >> s >> t >> l >> k;
	vector<vector<pair<int, int>>> adj(n + 1);
	bool vis1[n + 1];
	int diss[n + 1], dist[n + 1];
	for(int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].pb({b, c});
		adj[b].pb({a, c});
	}
	for(int i = 1; i <= n; i++) diss[i] = oo;
    diss[s] = 0;
	priority_queue<pair<int, int>> q1;
    q1.push({0, s});
    while(!q1.empty()) {
        int a = q1.top().second; 
		q1.pop();
        if(vis1[a]) continue;
        vis1[a] = true;
        for(auto u : adj[a]) {
           	int b = u.first, w = u.second;
           	if(diss[a] + w < diss[b]) {
               diss[b] = diss[a] + w;
               q1.push({-diss[b], b});
           	}
		} 
	}
	priority_queue<pair<int, int>> q2;
	q2.push({0, s});
    while(!q2.empty()) {
        int a = q2.top().second; 
		q2.pop();
        if(vis1[a]) continue;
        vis1[a] = true;
        for(auto u : adj[a]) {
           	int b = u.first, w = u.second;
           	if(dist[a] + w < dist[b]) {
               dist[b] = dist[a] + w;
               q1.push({-dist[b], b});
           	}
		} 
	}
	if(diss[t] <= k) {
		cout << n * (n - 1) / 2 << '\n';
		return 0;
	}
	sort(diss + 1, diss + n + 1);
	sort(dist + 1, dist + n + 1);
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		ans += upper_bound(dist + 1, dist + n + 1, k - l - diss[i]) - (dist + 1);
	}
    return 0;
}

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