Submission #1152214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152214		irmuun	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	228 ms	33256 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m;
    cin>>n>>m;
    ll S,T,L,K;
    cin>>S>>T>>L>>K;
    vector<pair<ll,ll>>g[n+5];
    for(ll i=1;i<=m;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        g[a].pb({b,c});
        g[b].pb({a,c});
    }
    vector<ll>dist(n+5,(ll)1e18);
    set<pair<ll,ll>>q;
    dist[S]=0;
    q.insert({0ll,S});
    while(!q.empty()){
        auto [d,i]=*q.begin();
        q.erase(q.begin());
        if(dist[i]!=d) continue;
        for(auto [j,w]:g[i]){
            if(dist[i]+w<dist[j]){
                dist[j]=dist[i]+w;
                q.insert({dist[j],j});
            }
        }
    }
    if(dist[T]<=K){
        cout<<n*(n-1)/2;
        return 0;
    }
    vector<vector<ll>>v;
    v.pb(dist);
    fill(all(dist),(ll)1e18);
    dist[T]=0;
    q.insert({0ll,T});
    while(!q.empty()){
        auto [d,i]=*q.begin();
        q.erase(q.begin());
        if(dist[i]!=d) continue;
        for(auto [j,w]:g[i]){
            if(dist[i]+w<dist[j]){
                dist[j]=dist[i]+w;
                q.insert({dist[j],j});
            }
        }
    }
    v.pb(dist);
    ll l[n+5],r[n+5];
    for(ll i=1;i<=n;i++){
        l[i]=v[0][i];
        r[i]=v[1][i];
    }
    sort(l+1,l+n+1);
    sort(r+1,r+n+1);
    ll ans=0;
    for(ll i=1;i<=n;i++){
        ll x=upper_bound(r+1,r+n+1,K-L-l[i])-r-1;
        ans+=x;
        // b<=K-L-a
    }
    cout<<ans;
}

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