Submission #1157032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157032		wjliangtpe	Construction Project 2 (JOI24_ho_t2)	C++20	45 / 100	63 ms	19872 KiB

Main

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,long long> > adj[200005];
long long d1[200005],d2[200005],k,ans=0;
int s,t,l,m,n,a,b,c;
#define oo 10000000000000001
priority_queue<pair<long long,int> > pq;
bitset<200005> vis;
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m>>s>>t>>l>>k;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    for(int i=1;i<=n;i++){
        d1[i]=oo;
        d2[i]=oo;
    }
    pq.push({d1[s]=0,s});
    while(!pq.empty()){
        auto p=pq.top();
        pq.pop();
        int v=p.second;
        if(vis[v]) continue;
        vis[v]=1;
        for(auto e:adj[v]){
            int u=e.first;
            long long w=e.second;
            if(d1[u]>d1[v]+w){
                d1[u]=d1[v]+w;
                pq.push({-d1[u],u});
            }
        }
    }
    pq.push({d2[t]=0,t});
    vis.reset();
    while(!pq.empty()){
        auto p=pq.top();
        pq.pop();
        int v=p.second;
        if(vis[v]) continue;
        vis[v]=1;
        for(auto e:adj[v]){
            int u=e.first;
            long long w=e.second;
            if(d2[u]>d2[v]+w){
                d2[u]=d2[v]+w;
                pq.push({-d2[u],u});
            }
        }
    }

    if(d1[t]<=k){
        cout<<n*(n-1)/2<<'\n';
        return 0;
    }
    sort(d1+1,d1+n+1),sort(d2+1,d2+n+1);
    /*int x=1,y=n;
    while(x<=n){
        while(d1[x]+d2[y]+l>k&&y>0) y--;
        x++;
        if(y<=0) break;
        ans+=y;
    }
    */
    for(int i=1;i<=n;i++){
        ans+=upper_bound(d2+1,d2+n+1,k-l-d1[i])-(d2+1);
    }
    cout<<ans<<'\n';
}

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