제출 #1077047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1077047		vyshniak_n	Construction Project 2 (JOI24_ho_t2)	C++17	100 / 100	264 ms	34740 KiB

Main

//#pragma optimize("Ofast")
//#pragma optimize("unroll-loops")
//#pragma traget("avx,avx2")
 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define el '\n'
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define point pair <ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
using namespace std;
 
#include <random>
mt19937 rnd(time(0));
 
const ll INF = 2e18 + 10;
const ll inf = 1e9 + 10;
const ll N = 2e5 + 10;
const ll mod = 1e9 + 7;
const ll LOG = 20;

vector <point> gr[N];

void solve() {
    ll n, m;
    cin >> n >> m;

    ll s, t, l, k;
    cin >> s >> t >> l >> k;

    for (ll i = 0; i < m; i++) {
        ll u, v, c;
        cin >> u >> v >> c;

        gr[u].pb({v, c});
        gr[v].pb({u, c});
    }

    auto bfs = [&](ll start) -> vector <ll> {
        vector <ll> dist(n + 1, INF);
        dist[start] = 0;
        dist[0] = -INF;

        set <point> st;
        st.insert({dist[start], start});

        while (!st.empty()) {
            ll v = st.begin()->ss;
            st.erase(st.begin());

            for (point to : gr[v]) {
                if (dist[to.ff] > dist[v] + to.ss) {
                    st.erase({dist[to.ff], to.ff});
                    dist[to.ff] = dist[v] + to.ss;
                    st.insert({dist[to.ff], to.ff});
                }
            }
        }

        return dist;
    };

    vector <ll> dist[2];
    dist[0] = bfs(s);
    dist[1] = bfs(t);

    if (dist[0][t] <= k)
        return void(cout << n * (n - 1) / 2 << el);

    ll ans = 0;

    sort(all(dist[0]));
    sort(all(dist[1]));

    for (ll i = 1; i <= n; i++) {
        ll lb, rb;

        lb = 0, rb = n + 1;
        while (lb + 1 < rb) {
            ll mid = (lb + rb) >> 1;

            if (dist[0][i] + l + dist[1][mid] <= k)
                lb = mid;
            else
                rb = mid;
        }
        ans += lb;

        lb = 0, rb = n + 1;
        while (lb + 1 < rb) {
            ll mid = (lb + rb) >> 1;

            if (dist[0][mid] + l + dist[1][i] <= k)
                lb = mid;
            else
                rb = mid;
        }
        ans += lb;
    }

    cout << ans / 2 << el;
    return;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    //freopen("deleg.in", "r", stdin);
    //freopen("deleg.out", "w", stdout);

    int tests = 1;
    //cin >> tests;
 
    while (tests--) 
        solve();
    return 0;
}
/*
*/

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