제출 #1059877

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1059877		anango	Construction Project 2 (JOI24_ho_t2)	C++17	100 / 100	319 ms	44068 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
int INF = 1LL<<61;

typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;


signed main() {
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        //freopen("input.txt", "r", stdin);
        // for writing output to output.txt
       // freopen("output.txt", "w", stdout);
    #endif
    #ifndef ONLINE_JUDGE
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
    #endif //fast IO
    int n,m; cin >> n >> m;
    int S,T,L,K; cin >> S >> T >> L >> K; S--; T--;
    vector<vector<pair<int,int>>> adjlist(n);
    for (int i=0; i<m; i++) {
        int u,v,w; cin >> u >> v >> w; u--; v--;
        adjlist[u].push_back({v,w}); adjlist[v].push_back({u,w});
    }
    vector<int> distS(n,INF);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> vals;
    distS[S] = 0; 
    for (int i=0; i<n; i++) {
        vals.push({distS[i],i});
    }
    while (vals.size()) {
        pair<int,int> fir = vals.top(); vals.pop();
        int u = fir.second; int dis = fir.first;
        if (dis>distS[u]) continue;
        for (pair<int,int> j:adjlist[u]) {
            if (dis+j.second<distS[j.first]) {
                vals.push({dis+j.second,j.first});
                distS[j.first] = dis+j.second;
            }
        }
    }

    vector<int> distT(n,INF);
    distT[T] = 0; 
    for (int i=0; i<n; i++) {
        vals.push({distT[i],i});
    }
    while (vals.size()) {
        pair<int,int> fir = vals.top(); vals.pop();
        int u = fir.second; int dis = fir.first;
        if (dis>distT[u]) continue;
        for (pair<int,int> j:adjlist[u]) {
            if (dis+j.second<distT[j.first]) {
                vals.push({dis+j.second,j.first});
                distT[j.first] = dis+j.second;
            }
        }
    }

    if (distS[T]<=K) {
        cout << n*(n-1)/2 << endl;
        return 0;
    }
    vector<int> s_sorted;
    for (int i=0; i<n; i++) {
        s_sorted.push_back(i);
    }
    sort(s_sorted.begin(), s_sorted.end(), [&](const int i1, const int i2) {
        return distS[i1]>distS[i2];
    }); //descending order to ensure distS[v]>distS[u]

    ordered_set distv;
    int su = 0;
    for (int i=0; i<n; i++) {
        int u =  s_sorted[i];
        int max_poss_weight = K-L-distS[u];
        su+=distv.order_of_key({max_poss_weight+1,-INF});

        distv.insert({distT[u],i});
    }
    cout << su << endl;

    
    for (int i=0; i<n; i++) {
        //cout << i <<" " << distS[i] << " " << distT[i] << endl;
    }
    
}

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