제출 #1152211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152211		dnnnda	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	228 ms	31652 KiB

Main

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define S second
#define F first
#define ll long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
const int X=1000000007;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> oset;

vector<pair<int,int>> adj[200005];
ll len[200005], alen[200005];

signed main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    memset(len,0x3f,sizeof len);
    memset(alen,0x3f,sizeof alen);
    int n, m; cin >> n >> m;
    ll s, t, L, K; cin >> s >> t >> L >> K;
    for(int i=1 ; i<=m ; i++){
        int u, v, c; cin >> u >> v >> c;
        adj[u].push_back({v,c});
        adj[v].push_back({u,c});
    }
    std::priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    len[s]=0;
    pq.push({0,s});
    while(!pq.empty()){
        auto[l,u]=pq.top();
        pq.pop();
        if(len[u]<l) continue;
        for(auto[v,c]:adj[u]) if(l+c<len[v]){
            len[v]=l+c;
            pq.push({len[v],v});
        }
    }
    if(len[t]<=K){
        cout << 1LL*n*(n-1)/2 << '\n';
        return 0;
    }
    alen[t]=0;
    pq.push({0,t});
    while(!pq.empty()){
        auto[l,u]=pq.top();
        pq.pop();
        if(alen[u]<l) continue;
        for(auto[v,c]:adj[u]) if(l+c<alen[v]){
            alen[v]=l+c;
            pq.push({alen[v],v});
        }
    }
    //for(int i=1 ; i<=n ; i++) cout << len[i] << (i==n ? '\n' : ' ');
    //for(int i=1 ; i<=n ; i++) cout << alen[i] << (i==n ? '\n' : ' ');
    oset st;
    ll ans=0;
    for(int i=1 ; i<=n ; i++) st.insert(alen[i]);
    for(int i=1 ; i<=n ; i++) ans+=st.order_of_key(K-L-len[i]+1);
    cout << ans << '\n';

    return 0;
}

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