Submission #1095700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095700		DucNguyen2007	Construction Project 2 (JOI24_ho_t2)	C++14	100 / 100	162 ms	28160 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
 
const int MAXN = 200001;
const ll INF = (ll)(1e18);
 
struct Node {
  int u;
  ll dis;
};
 
struct cmp {
  bool operator()(const Node &a, const Node &b) const {
    return a.dis > b.dis;
  }
};
 
int n, m, s, t, l;
ll dist[2][MAXN], ans, k;
bool vis[2][MAXN];
vector<pii> e[MAXN];
 
void dij(int S, bool op) {
  priority_queue<Node, vector<Node>, cmp> pq;
  for(int i = 1; i <= n; ++i) {
    dist[op][i] = INF;
    vis[op][i] = 0;
  }
  dist[op][S] = 0;
  pq.push({S, 0});
  for(; !pq.empty(); ) {
    auto [u, dis] = pq.top();
    pq.pop();
    if(vis[op][u]) {
      continue;
    }
    vis[op][u] = 1;
    for(auto [v, w] : e[u]) {
      if(dis + w < dist[op][v]) {
        dist[op][v] = dis + w;
        pq.push({v, dis + w});
      }
    }
  }
}
 
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m >> s >> t >> l >> k;
  for(int i = 1, u, v, w; i <= m; ++i) {
    cin >> u >> v >> w;
    e[u].emplace_back(v, w);
    e[v].emplace_back(u, w);
  }
  dij(s, 0);
  dij(t, 1);
  if(dist[0][t] <= k) {
    cout << 1ll * n * (n - 1) / 2;
    return 0;
  }
  sort(dist[0] + 1, dist[0] + n + 1);
  sort(dist[1] + 1, dist[1] + n + 1);
  for(int i = 1, j = n; i <= n; ++i) {
    for(; j > 0 && dist[0][i] + dist[1][j] + l > k; --j) {
    }
    ans += j;
  }
  cout << ans;
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dij(int, bool)':
Main.cpp:34:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     auto [u, dis] = pq.top();
      |          ^
Main.cpp:40:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |     for(auto [v, w] : e[u]) {
      |              ^

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