Submission #1179572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179572		nekolie	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	269 ms	22884 KiB

Main

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,s,t,c0,a,b,c;
    cin >> n >> m;
    long long k, odl[n+1][2], odp = 0;
    cin >> s >> t >> c0 >> k;
    vector<pair<int,int>> g[n+1];
    for (int i = 0; i < m; i++)
        cin >> a >> b >> c, g[a].push_back({b,c}), g[b].push_back({a,c});
    bool odw[n+1];
    for (int i = 1; i <= n; i++)
        odw[i] = false, odl[i][0] = odl[i][1] = 1000000000000000000;
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> q;
    odl[s][0] = odl[t][1] = 0, q.push({0,s});
    while (!q.empty()) {
        long long d = q.top().first;
        int v = q.top().second; q.pop();
        if (odw[v])
            continue;
        odw[v] = true;
        for (auto e : g[v])
            if (odl[e.first][0] > d+e.second)
                odl[e.first][0] = d+e.second, q.push({d+e.second,e.first});
    }
    if (odl[t][0] <= k)
        odp = 1ll*n*(n-1)/2;
    else {
        fill(odw,odw+n+1,false), q.push({0,t});
        while (!q.empty()) {
            long long d = q.top().first;
            int v = q.top().second; q.pop();
            if (odw[v])
                continue;
            odw[v] = true;
            for (auto e : g[v])
                if (odl[e.first][1] > d+e.second)
                    odl[e.first][1] = d+e.second, q.push({d+e.second,e.first});
        }
        vector<long long> v;
        for (int i = 1; i <= n; i++)
            v.push_back(odl[i][1]);
        sort(v.begin(),v.end());
        for (int i = 1; i <= n; i++) {
            int l = 0, r = n-1;
            while (l < r) {
                int mid = (l+r)/2;
                if (odl[i][0]+v[mid]+c0 > k)
                    r = mid;
                else
                    l = mid+1;
            }
            odp += l;
        }
    }
    cout << odp << endl;
    return 0;
}

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