Submission #1203285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203285		AlgorithmWarrior	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	216 ms	24848 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int const MAX=200005;
int n,m,s,t,l;
long long k;

struct edge{
    int nod;
    long long len;
};

vector<edge>G[MAX];

void read(){
    cin>>n>>m>>s>>t>>l>>k;
    int i;
    for(i=1;i<=m;++i){
        int a,b,len;
        cin>>a>>b>>len;
        G[a].push_back({b,len});
        G[b].push_back({a,len});
    }
}

class cmp{
public:
    bool operator()(edge a,edge b){
        return a.len>b.len;
    }
};

long long distS[MAX];
long long distT[MAX];

void djikstra(int nod,long long dist[]){
    priority_queue<edge,vector<edge>,cmp>pq;
    fill(dist,dist+MAX,1e18);
    dist[nod]=0;
    pq.push({nod,0});
    while(!pq.empty()){
        int nod_curr=pq.top().nod;
        long long len_curr=pq.top().len;
        pq.pop();

        if(len_curr>dist[nod_curr]){
            continue;
        }

        for(auto vec : G[nod_curr]){
            int nod_nou=vec.nod;
            long long len_nou=vec.len;
            if(dist[nod_nou]>len_curr+len_nou){
                dist[nod_nou]=len_curr+len_nou;
                pq.push({nod_nou,dist[nod_nou]});
            }
        }
    }
}

int get_pos(long long v[],int sz,long long nr){
    /// pos ult el <= nr
    /// [ )
    int st=1,dr=sz+1;
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(v[mij]<=nr){
            st=mij;
        }
        else{
            dr=mij;
        }
    }
    return st;
}

long long dS[MAX],dT[MAX];

long long solve(){
    djikstra(s,distS);
    djikstra(t,distT);

    if(distS[t]<=k){
        return 1LL*n*(n-1)/2;
    }

    int i;
    for(i=1;i<=n;++i){
        dS[i]=distS[i];
        dT[i]=distT[i];
    }

    sort(dS+1,dS+n+1);
    sort(dT+1,dT+n+1);

    long long rez=0;

    for(i=1;i<=n;++i){
        long long val=k-l-distS[i];
        if(val>=0){
            rez+=get_pos(dT,n,val);
        }
    }

    return rez;
}

void write(){
    cout<<solve();
}

int main()
{
    read();
    write();
    return 0;
}

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