Submission #1200436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200436		Valaki2	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	207 ms	24928 KiB

Main

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

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 2e5;
const int inf = 1e16 + 42;

int n, m;
int start, goal;
int len, total;
vector<pii > graph[1 + maxn];

vector<int> dijkstra(int source) {
    vector<bool> done(1 + n, false);
    vector<int> dist(1 + n, inf);
    priority_queue<pii > q;
    dist[source] = 0;
    q.push(mp(0, source));
    while(!q.empty()) {
        int cur = q.top().se;
        int cur_dist = -q.top().fi;
        q.pop();
        if(done[cur]) {
            continue;
        }
        done[cur] = true;
        for(pii nei : graph[cur]) {
            if(dist[nei.fi] > dist[cur] + nei.se) {
                dist[nei.fi] = dist[cur] + nei.se;
                q.push(mp(-dist[nei.fi], nei.fi));
            }
        }
    }
    return dist;
}

void solve() {
    cin >> n >> m;
    cin >> start >> goal >> len >> total;
    for(int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].pb(mp(b, c));
        graph[b].pb(mp(a, c));
    }
    vector<int> U = dijkstra(start), V = dijkstra(goal);
    if(U[goal] <= total) {
        cout << n * (n - 1) / 2 << "\n";
        return;
    }
    sort(U.begin() + 1, U.end());
    priority_queue<int> q;
    for(int i = 1; i <= n; i++) {
        q.push(V[i]);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        while(!q.empty() && U[i] + q.top() > total - len) {
            q.pop();
        }
        ans += q.size();
    }
    cout << ans << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // int T = 1; cin >> T; while(T--)
    solve();
}

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