Submission #1195952

#TimeUsernameProblemLanguageResultExecution timeMemory
1195952quangminh412Construction Project 2 (JOI24_ho_t2)C++20
100 / 100
128 ms23340 KiB
#include <bits/stdc++.h> using namespace std; /* Ben Watson Handle codeforces : quangminh98 Mua Code nhu mua Florentino !! */ #define ll long long const string name = "test"; void solve(); signed main() { if (fopen((name + ".inp").c_str(), "r")) { freopen((name + ".inp").c_str(), "r", stdin); freopen((name + ".out").c_str(), "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; } // main program const int maxn = 2e5 + 1; const ll oo = 0x3f3f3f3f3f3f3f3f; vector<pair<int, int>> adj[maxn]; int n, m, s, t, l; ll k; vector<ll> Dijkstra(int source) { vector<ll> dist(n + 1, oo); priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; pq.push({dist[source] = 0, source}); while (!pq.empty()) { int u = pq.top().second; ll w = pq.top().first; pq.pop(); if (dist[u] != w) continue; for (pair<int, int> nxt : adj[u]) { int v = nxt.first, w = nxt.second; if (dist[v] > dist[u] + w) pq.push({dist[v] = dist[u] + w, v}); } } return dist; } void solve() { cin >> n >> m >> s >> t >> l >> k; for (int i = 0; i < m; i++) { int u, v, c; cin >> u >> v >> c; adj[u].push_back({v, c}); adj[v].push_back({u, c}); } vector<ll> S = Dijkstra(s), T = Dijkstra(t); if (S[t] <= k) { cout << 1ll * n * (n - 1) / 2 << '\n'; return; } sort(S.begin() + 1, S.end()); sort(T.begin() + 1, T.end()); ll res = 0; for (int i = 1; i <= n; i++) { int pos = upper_bound(T.begin() + 1, T.end(), k - l - S[i]) - T.begin(); res += pos - 1; } cout << res << '\n'; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...