Submission #1309050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309050		IUA_Hasin	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	436 ms	72044 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
 
#define ll                                  long long
#define ld                                  long double
#define endl                                "\n"
#define yeap                                cout<<"YES"<<endl
#define nope                                cout<<"NO"<<endl
#define all(v)                              v.begin(), v.end()

using namespace std;
using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;


const ll infp = 1e18;
const ll infn = 1e18 * (-1);

const ll N = 2e6 + 10;
const ll M = 5e3 + 10;
const ll MOD = 998244353;


ll hceil(ll a, ll b){
    return (a+b-1)/b;
}

vector<pair<ll, ll>> graph[N];
vector<ll> dist(N, infp), vis(N, 0LL);

void dijkstra(ll source){
    set<pair<ll, ll>> s;
    s.insert({0, source});
    dist[source] = 0;

    while(s.size()>0){
        auto node = *s.begin();
        ll v = node.second;
        ll v_dist = node.first;
        s.erase(s.begin());
        if(vis[v]==0){
            for(auto child : graph[v]){
                ll v2 = child.first;
                ll wt = child.second;
                if((dist[v]+wt)<(dist[v2])){
                    dist[v2] = dist[v]+wt;
                    s.insert({dist[v2], v2});
                }
            }
            vis[v] = 1;
        }
    }
    
}

void solve(ll testcase){
    ll n, m, s, t, l, k;
    cin>>n>>m>>s>>t>>l>>k;

    for(int i=1; i<=m; i++){
        ll a, b, c;
        cin>>a>>b>>c;

        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }

    ordered_multiset<ll> sts, stt;

    dijkstra(s);
    for(int i=1; i<=n; i++){
        sts.insert(dist[i]);
    }
    for(int i=1; i<=n; i++){
        vis[i] = 0, dist[i] = infp;
    }

    dijkstra(t);
    for(int i=1; i<=n; i++){
        stt.insert(dist[i]);
    }    

    if(dist[s]<=k){
        cout << (n * (n-1)) / 2 << endl;
    } else if(l > k){
        cout << 0 << endl; 
    } else {
        ll ans = 0;
        for(int i=1; i<=n; i++){
            ll temp = k - l - dist[i];
            ans += sts.order_of_key(temp + 1);
        }

        cout << ans << endl;
    }

    
    

    
    
    
}

int main(){
    #if __has_include("LOCAL.hh")
        #include "LOCAL.hh"
    #endif
 
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output3.txt", "w", stdout);
        using namespace std::chrono;
        cout << fixed << setprecision(9);
        auto begin = steady_clock::now();
    #else
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif

    int T = 1; 
    //cin>>T;
    for(int i=1; i<=T; i++){
        solve(i);
    }



 
 
    #ifdef LOCAL
        auto end = steady_clock::now();
        cout << "\nTime : " 
             << (ld)duration_cast<nanoseconds>
                (end - begin).count()/1000000000 
             << "s" << endl;
    #endif
 
 
    return 0;
}

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