제출 #1272138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272138		tvgk	Construction Project 2 (JOI24_ho_t2)	C++20	45 / 100	31 ms	11432 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define fi first
#define se second
#define ii pair<ll, ll>
const int mxN = 1e5 + 7;
const ll inf = 1e18;

int n, m, s, t;
ll mn[mxN][2], ex, lim;
ii val[mxN];
map<ll, int> mp;
vector<ii> w[mxN];
vector<ll> tree[mxN * 4];

void Dij(int tt, int j)
{
    for (int i = 1; i <= n; i++)
        mn[i][tt] = inf;

    priority_queue<ii, vector<ii>, greater<ii>> pq;
    pq.push({0, j});
    mn[j][tt] = 0;

    while (pq.size())
    {
        ii j = pq.top();
        pq.pop();

        if (j.fi != mn[j.se][tt])
            continue;

        for (ii i : w[j.se])
        {
            if (mn[i.fi][tt] > j.fi + i.se)
            {
                mn[i.fi][tt] = j.fi + i.se;
                pq.push({j.fi + i.se, i.fi});
            }
        }
    }
}

void Build(int j = 1, int l = 1, int r = n)
{
    if (l == r)
    {
        tree[j].push_back(val[l].se);
        return;
    }

    int mid = (l + r) / 2;
    Build(j * 2, l, mid);
    Build(j * 2 + 1, mid + 1, r);
    merge(tree[j * 2].begin(), tree[j * 2].end(), tree[j * 2 + 1].begin(), tree[j * 2 + 1].end(), back_inserter(tree[j]));
}

ll Get(ll vt, ll dif, int j = 1, int l = 1, int r = n)
{
    if (vt < val[l].fi)
        return 0;

    if (val[r].fi <= vt)
    {
        int u = lower_bound(tree[j].begin(), tree[j].end(), dif) - tree[j].begin();
        int v = upper_bound(tree[j].begin(), tree[j].end(), dif) - tree[j].begin();
        mp[dif] += v - u;
        return r - l + 1 - v;
    }

    int mid = (l + r) / 2;
    return Get(vt, dif, j * 2, l, mid) + Get(vt, dif, j * 2 + 1, mid + 1, r);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> m;
    cin >> s >> t >> ex >> lim;

    for (int i = 1; i <= m; i++)
    {
        int u, v, cost;
        cin >> u >> v >> cost;
        w[u].push_back({v, cost});
        w[v].push_back({u, cost});
    }
    Dij(0, s);
    Dij(1, t);

    for (int i = 1; i <= n; i++)
        val[i] = {mn[i][1], mn[i][0] - mn[i][1]};
    sort(val + 1, val + n + 1);
    Build();

//    for (int i = 1; i <= n; i++)
//        cout << val[i].fi << " " << val[i].se << " : ";
//    cout << '\n';

    if (mn[t][0] <= lim)
    {
        cout << n * (n - 1) / 2;
        return 0;
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        mn[i][1] = mn[i][0] - mn[i][1];
        ans += Get(lim - (mn[i][0] + ex), mn[i][1]);
    }

    for (int i = 1; i <= n; i++)
    {
        ans += mp[mn[i][1]] / 2;
        mp[mn[i][1]] = 0;
    }
    cout << ans;
}

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