Submission #1212479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212479		mdn2002	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	309 ms	53464 KiB

Main

/*
Mayoeba Yabureru
*/
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

long long dis[2][200002];
vector<vector<int>> gr[200002];

void solve() {
  long long n, m, s, t, l, k;
  cin >> n >> m >> s >> t >> l >> k;

  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    gr[a].push_back({b, c});
    gr[b].push_back({a, c});
  }

  long long kl = k - l;
  // a + b <= kl

  for (int i = 0; i <= 1; i ++) {
    for (int j = 1; j <= n; j ++) dis[i][j] = 1e17;
  }

  dis[0][s] = 0;
  dis[1][t] = 0;

  priority_queue<vector<long long>> pq;
  pq.push({0, 0, s});
  pq.push({0, 1, t});

  while (!pq.empty()) {
    auto p = pq.top();
    pq.pop();

    if (-p[0] > dis[p[1]][p[2]]) continue;
    int c = p[1], v = p[2];

    for (auto u : gr[v]) {
      if (dis[c][u[0]] > dis[c][v] + u[1]) {
        dis[c][u[0]] = dis[c][v] + u[1];
        pq.push({-dis[c][u[0]], c, u[0]});
      }
    }
  }

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

  vector vs(0, 0ll), vt(0, 0ll);

  for (int i = 1; i <= n; i++) {
    vs.push_back(dis[0][i]);
    vt.push_back(dis[1][i]);
  }

  sort(vs.rbegin(), vs.rend());
  sort(vt.begin(), vt.end());

  long long ans = 0;

  int j = 0;
  for (int i = 0; i < vs.size(); i++) {
    while (j < vt.size() && vs[i] + vt[j] <= kl) {
      j++;
    }
    ans += j;
  }

  for (int i = 1; i <= n; i ++) {
    if (dis[0][i] + dis[1][i] + l <= k) ans --;
  }
  cout << ans << endl;
}

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

  int T = 1;
  for (int I = 1; I <= T; I++) {
    solve();
  }
}

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