Submission #1127623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127623		Warinchai	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	293 ms	24256 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int,int>>adj[200005];
int diss[200005];
int dist[200005];
int inf=1e18;
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;cin>>n>>m;
    int s,t,l,k;cin>>s>>t>>l>>k;
    for(int i=0;i<m;i++){
        int a,b,c;cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    for(int i=1;i<=n;i++)diss[i]=dist[i]=inf;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    pq.push({0,s});
    while(!pq.empty()){
        auto [dis,x]=pq.top();
        pq.pop();
        if(diss[x]!=inf)continue;
        diss[x]=dis;
        for(auto v:adj[x])pq.push({dis+v.second,v.first});
    }
    pq.push({0,t});
    while(!pq.empty()){
        auto [dis,x]=pq.top();
        pq.pop();
        if(dist[x]!=inf)continue;
        dist[x]=dis;
        for(auto v:adj[x])pq.push({dis+v.second,v.first});
    }
    if(diss[t]<=k){
        cout<<n*(n-1)/2;
        return 0;
    }
    vector<int>v;
    for(int i=1;i<=n;i++)v.push_back(dist[i]);
    sort(v.begin(),v.end());
    int ans=0;
    for(int i=1;i<=n;i++){
        int dis=k-(diss[i]+l);
        //cerr<<dis<<"\n";
        int id=upper_bound(v.begin(),v.end(),dis)-v.begin();
        ans+=id;
    }
    cout<<ans;
}

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