Submission #1265784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265784		flashmt	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	244 ms	24040 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const long long oo = 1LL << 50;

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m, s, t, l;
  long long k;
  cin >> n >> m >> s >> t >> l >> k;
  s--; t--;
  vector<vector<pair<int, int>>> a(n);
  while (m--)
  {
    int x, y, z;
    cin >> x >> y >> z;
    a[--x].push_back({--y, z});
    a[y].push_back({x, z});
  }

  auto calcDist = [&](int from)
  {
    vector<long long> dist(n, oo);
    vector<int> flag(n);
    dist[from] = 0;
    priority_queue<pair<long long, int>> q;
    q.push({0, from});
    while (!empty(q))
    {
      auto [_, x] = q.top();
      q.pop();
      if (flag[x])
        continue;
      flag[x] = 1;
      for (auto [y, w] : a[x])
        if (!flag[y] && dist[x] + w < dist[y])
        {
          dist[y] = dist[x] + w;
          q.push({-dist[y], y});
        }
    }
    return dist;
  };

  auto distS = calcDist(s), distT = calcDist(t);
  if (distS[t] <= k)
  {
    cout << n * (n - 1LL) / 2 << endl;
    return 0;
  }

  vector<int> idS(n);
  iota(begin(idS), end(idS), 0);
  auto idT = idS;
  sort(begin(idS), end(idS), [&](int u, int v) { return distS[u] < distS[v]; });
  sort(begin(idT), end(idT), [&](int u, int v) { return distT[u] > distT[v]; });

  long long ans = 0;
  for (int i = 0, j = 0; i < n && j < n;)
  {
    int x = idS[i], y = idT[j];
    if (distS[x] + distT[y] > k - l) j++;
    else
    {
      ans += n - j;
      i++;
    }
  }

  for (int i = 0; i < n; i++)
    if (distS[i] + distT[i] <= k - l)
      ans--;

  cout << ans << endl;
}

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