Submission #1013913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013913		Baytoro	Construction Project 2 (JOI24_ho_t2)	C++17	100 / 100	506 ms	48188 KiB

Main

#include <bits/stdc++.h>


#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define orderedset tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define int ll
#define all(x) x.begin(),x.end()
const int N=2e5+5;
vector<pair<int,int>> g[N];
vector<int> dist1,dist2;
void djks(int x, int c) {
    vector<int> dist(N,1e18);

    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    pq.push({0,x});
    dist[x]=0;
    while(!pq.empty()) {
        int k=pq.top().sc;
        int d=pq.top().fr;
        pq.pop();
        if(dist[k]!=d) continue;
        for(auto it: g[k]) {
            if(dist[it.fr]>d+it.sc) {
                dist[it.fr]=d+it.sc;
                pq.push({dist[it.fr],it.fr});
            }
        }
    }
    if(c==0) dist1=dist;
    else dist2=dist;
}
void solve(){
    int n,m;cin>>n>>m;
    int s,t,l,k;cin>>s>>t>>l>>k;
    for(int i=0;i<m;i++) {
        int a,b,c;cin>>a>>b>>c;
        g[a].pb({b,c});
        g[b].pb({a,c});
    }
    djks(s,0);
    djks(t,1);
    if(dist1[t]<=k) {
        cout<<n*(n-1)/2;
        return;
    }
    int ans=0;
    orderedset a,b;
    a.insert(1e18);
    b.insert(1e18);
    for(int i=1;i<=n;i++){
        int A=a.order_of_key(k-(dist1[i]+l)+1);
        int B=b.order_of_key(k-(dist2[i]+l)+1);
        //cout<<A<<' '<<B<<endl;
        ans+=A;
        ans+=B;
        a.insert(dist2[i]);
        b.insert(dist1[i]);
    }
    cout<<ans<<endl;
}
signed main(){
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
}
//#endif

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