제출 #1182710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182710		enkhochir	Construction Project 2 (JOI24_ho_t2)	C++20	0 / 100	4 ms	8260 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define int long long
typedef tree<
int,
null_type,
less_equal<int>,
rb_tree_tag,
tree_order_statistics_node_update> 
ordered_set;
vector<pair<int,int>> adj[200005];
int n,m;
int s,t,l,k;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cin>>n>>m;
    cin>>s>>t>>l>>k;
    for(int i=0; i<m; i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({w,v});
        adj[v].push_back({w,u});
    }
    vector<int> d1(200005,1e18);
    vector<int> d2(200005,1e18);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    d1[s]=0;
    q.push({0,s});
    while(!q.empty()){
        int w=q.top().first, node=q.top().second;
        q.pop();
        if(w!=d1[node]) continue;
        for(pair<int,int> &j: adj[node]){
            int nw=j.first+w, next=j.second;
            if(d1[next]>nw){
                d1[next]=nw;
                q.push({nw,next});
            }
        }
    }
    while(!q.empty()) q.pop();
    d2[t]=0;
    q.push({0,t});
    while(!q.empty()){
        int w=q.top().first, node=q.top().second;
        q.pop();
        if(w!=d2[node]) continue;
        for(pair<int,int> &j: adj[node]){
            int nw=j.first+w, next=j.second;
            if(d2[next]>nw){
                d2[next]=nw;
                q.push({nw,next});
            }
        }
    }
    int kk=0;
    for(int i=1; i<=n; i++){
        for(int j=i+1; j<=n; j++){
            if(d1[i]+d2[j]+l<=k){
                kk++;
            }
        }
    }
    cout<<kk<<endl;
    return 0;
    ordered_set s,t;
    for(int i=1; i<=n; i++){
        s.insert(d1[i]);
    }
    for(int i=1; i<=n; i++){
        t.insert(d2[i]);
    }
    int ans=0;
    for(int i=1; i<=n; i++){
        ans+=t.order_of_key(k-l-d1[i]+1);
        ans+=s.order_of_key(k-l-d2[i]+1);
    }
    cout<<ans<<endl;
}

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