Submission #1274904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274904		hssaan_arif	Construction Project 2 (JOI24_ho_t2)	C++20	0 / 100	2 ms	580 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 = 3e5 + 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;
    int t = -1;
    for (int i = 0 ; i < m ; i++){
        cin >> u >> v >> w;
        lis[u].pb({w , v});
        lis[v].pb({w , u});
        if (t == -1){
            t = w;
            continue;
        }
        if (t != w){
            cout << 0 << endl;
            return;
        }
    }
    if (!(L == 1 && K == 2)){
        cout << 0 << endl;
        return;
    }
    get(S , 1);
    get(T , 0);
    if (ds[T] <= 2){
        cout << (n * (n+1))/2 << endl;
    }else{
        int ans = 1 + lis[T].size() + lis[S].size();
        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: 0 / 16
• Subtask 3: 0 / 29
• Subtask 4: 0 / 47