Submission #1274892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274892		hssaan_arif	Construction Project 2 (JOI24_ho_t2)	C++20	45 / 100	9 ms	844 KiB

Main

// #include <me>
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define pb push_back
#define int long long
#define fi first
#define se second

const int N = 3e3 + 5, M = 1e9 + 7, LG = 20;

int n , m , S , T , L , K , ds[N] , u , v , w , dt[N];
vector<pair<int,int>> lis[N];

void get(int s , bool r){
    if (r){
        bool V[N] = {};
        set<pair<int,int>> st;
        for (int i = 1 ; i <= n ; i++){
            ds[i] = 1e18;
        }
        ds[s] = 0;
        V[s] = 1;
        int cn = 1;
        for (auto i : lis[s]){
            st.insert({i.fi , i.se});
        }
        while(cn != n && st.size()){
            int v = (*st.begin()).se , w = (*st.begin()).fi;
            st.erase((*st.begin()));
            if (V[v]) continue;
            cn++;
            // cout << u << ' ' << v << ' ' << w << endl;
            V[v] = 1;
            ds[v] = w;
            for (auto i : lis[v]){
                st.insert({i.fi + ds[v] , i.se});
            }
        }
    }else{
        bool V[N] = {};
        set<pair<int,int>> st;
        for (int i = 1 ; i <= n ; i++){
            dt[i] = 1e18;
        }
        dt[s] = 0;
        V[s] = 1;
        int cn = 1;
        for (auto i : lis[s]){
            st.insert({i.fi , i.se});
        }
        while(cn != n && st.size()){
            int v = (*st.begin()).se , w = (*st.begin()).fi;
            st.erase((*st.begin()));
            if (V[v]) continue;
            cn++;
            // cout << u << ' ' << v << ' ' << w << endl;
            V[v] = 1;
            dt[v] = w;
            for (auto i : lis[v]){
                st.insert({i.fi + dt[v] , i.se});
            }
        }
    }
    
}

void solve(){
    cin >> n >> m;
    cin >> S >> T >> L >> K;
    for (int i = 0 ; i < m ; i++){
        cin >> u >> v >> w;
        lis[u].pb({w , v});
        lis[v].pb({w , u});
    }
    get(S , 1);
    get(T , 0);
    int ans = 0 ;
    for (int i = 1 ; i <= n ; i++){
        for (int j = i+1 ; j <= n ; j++){
            int di = min({ds[T] , ds[i] + L + dt[j], ds[j] + L + dt[i]});
            if (di <= K) ans++;
        }
    }
    cout << ans << endl;
    

}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ts = 1;
    // cin >> ts;
    while(ts--){
        solve();
    }
}

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