제출 #1277655

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277655		tunademayo	Construction Project 2 (JOI24_ho_t2)	C++20	8 / 100	114 ms	23204 KiB

Main

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

#define ll long long

const bool Multitest = 0;

const int N = 2e5 + 10;

int a[N];
vector<pair<int, int>> adj[N];
int n, m, l; ll k;
int s, t; ll d[5][N];

struct Data
{
    int u; ll w;

    Data(int _u, int _w) : u(_u), w(_w) {}
};

struct cmp
{
    bool operator() (Data a, Data b)
    {
        return a.w > b.w;
    }
};

void dijsktra(int s, int id)
{
    priority_queue<Data, vector<Data>, cmp> q;

    for(int i = 1 ; i <= n ; i++) d[id][i] = 1e18;

    q.push(Data(s, 0));

    d[id][s] = 0;

    while(!q.empty())
    {
        Data x = q.top(); q.pop();

        if(d[id][x.u] != x.w) continue;

        for(auto [v, w] : adj[x.u])
        {
            if(d[id][v] > x.w + w)
            {
                d[id][v] = x.w + w;
                q.push(Data(v, d[id][v]));
            }
        }
    }
}

void Work()
{
    cin >> n >> m;

    cin >> s >> t >> l >> k;

    for(int i = 1 ; i <= m ; i++)
    {
        int u, v, w;    cin >> u >> v >> w;

        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    dijsktra(s, 1);
    dijsktra(t, 2);

    if(d[1][t] <= k)
    {
        cout << 1ll * (n - 1) * n / 2 << '\n';

        return;
    }

    sort(d[1] + 1, d[1] + 1 + n);
    sort(d[2] + 1, d[2] + 1 + n);

    ll ans = 0;

    for(int i = 1 ; i <= n ; i++)
    {
        int li = 1, ri = n, pos = 0;

        while(li <= ri)
        {
            int mid = (li + ri) >> 1;

            if(d[1][i] + d[2][mid] + l <= k)
            {
                li = mid + 1, pos = mid;
            }
            else ri = mid - 1;
        }
        ans += pos;
    }

    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int q = 1;

    if(Multitest)   cin >> q;

    while(q--) Work();
}

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