Submission #1212465

#TimeUsernameProblemLanguageResultExecution timeMemory
1212465mdn2002Construction Project 2 (JOI24_ho_t2)C++20
53 / 100
2095 ms53456 KiB
/* Mayoeba Yabureru */ #pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> using namespace std; void solve() { long long n, m, s, t, l, k; cin >> n >> m >> s >> t >> l >> k; vector gr(n + 1, vector(0, vector(0, 0ll))); 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 vector dis(2, vector(n + 1, 100000000000000000)); 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(); 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(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...