Submission #1242219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242219		nasjes	Construction Project 2 (JOI24_ho_t2)	C++20	53 / 100	2096 ms	42484 KiB

Main

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 1e6+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e18 + 77;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, m;
ll l, t;
vector<pll> a[dim];
ll dst1[dim];
ll dst2[dim];


int main() {
    cin>>n>>m;
    ll s, f;
    cin>>s>>f>>l>>t;
    for(int i=1; i<=m; i++){
        ll u, v, w;
        cin>>u>>v>>w;
        a[u].pb({v, w});
        a[v].pb({u, w});
    }
    for(int i=1; i<=n; i++){
        dst1[i]=inf;
        dst2[i]=inf;
    }
    priority_queue<pll, vector<pll>, greater<pll>> q;
    q.push({0, s});
    dst1[s]=0;
    while(q.size()>0){
        ll v=q.top().se;
        q.pop();
        for(auto x: a[v]){
            if(dst1[x.fi]>dst1[v]+x.se){
                dst1[x.fi]=dst1[v]+x.se;
                q.push({dst1[x.fi], x.fi});
            }
        }
    }
    q.push({0, f});
    dst2[f]=0;
    while(q.size()>0){
        ll v=q.top().se;
        q.pop();
        for(auto x: a[v]){
            if(dst2[x.fi]>dst2[v]+x.se){
                dst2[x.fi]=dst2[v]+x.se;
                q.push({dst2[x.fi], x.fi});
            }
        }
    }
    if(dst1[f]<=t){
        cout<<(n)*(n-1)/2<<endl;
        return 0;
    }
    //cout<<dst1[4]<<endl;
    sort(dst2+1, dst2+1+n);
    ll cnt=0;
    for(int i=1; i<=n; i++){
        auto id=upper_bound(dst2+1, dst2+1+n, t-l-dst1[i]);
        ll d=distance(dst2+1, id);
        cnt+=d;
    }
    cout<<cnt<<endl;
    return 0;
}

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