Submission #1274922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274922		ghammazhassan	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	227 ms	27360 KiB

Main

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;
#define int long long
#define endl "\n"
#define fi first
#define se second
const int M=998244353;
const int inf = 1e16;
const int LOG=20;
const int N=2e5+5;
int n , m , c , w , k , t=1 , q=1 , x , y , z , l , r;
vector<pair<int,int>>a[N];
int di[N],di2[N];
int vi[N],vi2[N];
void solve()
{   
    cin >> n >> m;
    int s,t;
    cin >> s >> t >> l >> k;
    for (int i=0;i<m;i++){
        cin >> x >> y >> z;
        a[x].push_back({y,z});
        a[y].push_back({x,z});
    }
    for (int i=1;i<=n;i++){
        di[i]=inf;
        di2[i]=inf;
    }
    priority_queue<pair<int,int>>o;
    di[s]=0;
    o.push({0,s});
    while (o.size()){
        auto h1=o.top();
        int h=h1.se;
        o.pop();
        if (vi[h])continue;
        vi[h]=1;
        di[h]=-h1.fi;
        for (auto [i,j]:a[h]){
            if (vi[i])continue;
            o.push({-1*(di[h]+j),i});
        }
    }
    di2[t]=0;
    o.push({0,t});
    while (o.size()){
        auto h1=o.top();
        int h=h1.se;
        o.pop();
        if (vi2[h])continue;
        vi2[h]=1;
        di2[h]=-h1.fi;
        for (auto [i,j]:a[h]){
            if (vi2[i])continue;
            o.push({-1*(di2[h]+j),i});
        }
    }
    if (di[t]>k){
        vector<int>d;
        d.push_back(0);
        d.push_back(inf);
        for (int i=1;i<=n;i++){
            d.push_back(di[i]);
        }
        sort(d.begin(),d.end());
        c=0;
        for (int i=1;i<=n;i++){
            x=di2[i];
            int li=0;
            int hi=n+1;
            int mi=(li+hi)/2;
            while (li<hi){
                if (d[mi]+x+l<=k){
                    li=mi;
                }
                else{
                    hi=mi-1;
                }
                mi=(li+hi+1)/2;
            }
            c+=mi;
        }
        cout << c << endl;
    }
    else{
        cout << n*(n-1)/2 << endl;
    }


}
signed main()    
{
    ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    cin.tie(0), cout.tie(0);//DO NOT USE IN INTERACTIVE
    cout << fixed << setprecision(9);
    srand(time(0));
    // int t=1;
    // cin >> t;
    for (int _=1;_<=t;_++){
        solve();
        q++;
    }
} 

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