Submission #1170728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170728		Craftless	Construction Project 2 (JOI24_ho_t2)	C++20	8 / 100	120 ms	26912 KiB

Main

#include <bits/stdc++.h>

#define int long long int
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define INF 1e13

using namespace std;

// remove edges going back, only consider going forward
// find distances to E at each node, then only pair if d[v] + L < d[u]
// for each u, find a v such that d[v] < d[u] - L (saves time), dd[u] + d[v] + L <= K

int N, M, S, E, L, K, ans;
vector<pi> adjlist[200010];

using namespace std;

int32_t main() {

    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N >> M >> S >> E >> L >> K;

    for (int i = 0; i < M; i++) {
        int a,b,c; cin>>a>>b>>c;
        adjlist[a].pb({ c, b });
        adjlist[b].pb({ c, a });
    }

    vector<int> distS(N + 1, INF);
    priority_queue<pi, vector<pi>, greater<pi>> pq1;
    distS[S] = 0;
    pq1.push({0,S});
    while (!pq1.empty()) {
        auto [d,u] = pq1.top();pq1.pop();
        if(d > distS[u])continue;
        for(auto [w,v]: adjlist[u]){
            if(distS[u] + w >= distS[v])continue;
            distS[v] = distS[u] + w;
            pq1.push({distS[v],v});
        }
    }

    vector<int> distE(N + 1, INF);
    priority_queue<pi, vector<pi>, greater<pi>> pq2;
    distE[E] = 0;
    pq2.push({0,E});
    while (!pq2.empty()) {
        auto [d,u] = pq2.top();pq2.pop();
        if(d > distE[u])continue;
        for(auto [w,v]: adjlist[u]){
            if(distE[u] + w >= distE[v])continue;
            distE[v] = distE[u] + w;
            pq2.push({distE[v],v});
        }
    }

    if (distS[E] <= K) {
        cout << ((N * (N - 1)) / 2) << "\n";
        return 0;
    }

    vector<int> ls(distS), le(distE);
    sort(ls.begin(), ls.end());
    sort(le.begin(), le.end());

    for (int i = 1; i <= N; i++) {
        int stuff = (upper_bound(le.begin(), le.end(), K - L - distS[i]) - le.begin());
        if (distE[i] <= K - L - distS[i]) stuff--; // comment uncomment
        // cout << stuff << " ";
        ans += stuff;
    }
    // cout << endl;
    // for (int i = 1; i <= N; i++) {
    //     cout << i << " ";
    // }
    // cout << endl;
    // for (int i = 1; i <= N; i++) {
    //     cout << distS[i] << " ";
    // }
    // cout << endl;
    // for (int i = 1; i <= N; i++) {
    //     cout << distE[i] << " ";
    // }

    cout << ans << "\n";

    return 0;    
}

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