Submission #1262410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262410		notisora	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	149 ms	24360 KiB

Main

///NotIsora
///This is my last dance
#include<bits/stdc++.h>
#define modulo 1000000007
#define fi first
#define se second
#define sq(x) (x)*(x)
#define ll long long
#define ld long double
#define el '\n'
#define pb push_back
///#define int long long

using namespace std;

const int N=2e5+5;
const ll INF=1e18;

int n,m;
int st,ed,l;
ll k;
ll d[2][N];
vector<pair<int,int>>adj[N];

struct State{
    int s,type;
    ll dis;
    bool operator < (const State&other) const{
        return dis>other.dis;
    }
};

bool check(){
    if (l!=1 || k!=2) return 0;
    for(int i=1;i<=n;i++){
        for(pair<int,int>&pr:adj[i]){
            if (pr.se!=1){
                return 0;
            }
        }
    }
    return 1;
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("i.INP","r",stdin);
    cin>>n>>m;
    cin>>st>>ed>>l>>k;
    for(int i=1;i<=m;i++){
        int a,b,w;
        cin>>a>>b>>w;
        adj[a].pb({b,w});
        adj[b].pb({a,w});
    }

    for(int i=1;i<=n;i++){
        d[0][i]=d[1][i]=INF;
    }

    priority_queue<State>pq;

    d[0][st]=0;
    d[1][ed]=0;
    pq.push({st,0,0LL});
    pq.push({ed,1,0LL});

    while(!pq.empty()){
        int s=pq.top().s;
        int t=pq.top().type;
        ll dis=pq.top().dis;
        pq.pop();

        if (dis>d[t][s]) continue;

        for(pair<int,int>&pr:adj[s]){
            int u=pr.fi;
            int w=pr.se;
            if (d[t][u]>d[t][s]+(ll)w){
                d[t][u]=d[t][s]+(ll)w;
                pq.push({u,t,d[t][u]});
            }
        }
    }

    ll ans=0;
    if (d[0][ed]<=k){
        cout<<1LL*n*(n-1)/2;
        return 0;
    }
//    if (check()){
//        int stcnt=0,edcnt=0;
//
//        for(int i=1;i<=n;i++){
//            if (d[0][i]==1) stcnt++;
//            if (d[1][i]==1) edcnt++;
//        }
//        ans+=(ll)stcnt;
//        ans+=(ll)edcnt;
//        ans++;
//        cout<<ans;
//        return 0;
//    }
    sort(d[0]+1,d[0]+1+n);

//    for(int i=1;i<=n;i++){
//        cout<<d[1][i]<<el;
//    }
//    cout<<el;

    for(int i=1;i<=n;i++){
        ll val=k-d[1][i]-l;
//        cout<<val<<el;

        int idx=upper_bound(d[0]+1,d[0]+1+n,val)-d[0];

        ans+=(ll)idx-1ll;
    }
    cout<<ans;
}

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