Submission #1274980

#TimeUsernameProblemLanguageResultExecution timeMemory
1274980hynmjConstruction Project 2 (JOI24_ho_t2)C++20
53 / 100
2096 ms31192 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> #define pi pair<int, int> #define int long long #define ff first #define ss second const int N = 2e5 + 7; using namespace std; vector<pi> graph[N]; namespace __gnu_pbds { typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; } using namespace __gnu_pbds; void Insert(ordered_set &s, int x) { // this function inserts one more occurrence of (x) into the set. s.insert(x); } bool Exist(ordered_set &s, int x) { // this function checks weather the value (x) exists in the set or not. if ((s.upper_bound(x)) == s.end()) { return 0; } return ((*s.upper_bound(x)) == x); } void Erase(ordered_set &s, int x) { // this function erases one occurrence of the value (x). if (Exist(s, x)) { s.erase(s.upper_bound(x)); } } int FirstIdx(ordered_set &s, int x) { // this function returns the first index of the value (x)..(0 indexing). // if (!Exist(s, x)) // { // return -1; // } return (s.order_of_key(x)); } int Value(ordered_set &s, int idx) { // this function returns the value at the index (idx)..(0 indexing). return (*s.find_by_order(idx)); } int LastIdx(ordered_set &s, int x) { // this function returns the last index of the value (x)..(0 indexing). if (!Exist(s, x)) { return -1; } if (Value(s, (int)s.size() - 1) == x) { return (int)(s.size()) - 1; } return FirstIdx(s, *s.lower_bound(x)) - 1; } int Count(ordered_set &s, int x) { // this function returns the number of occurrences of the value (x). if (!Exist(s, x)) { return 0; } return LastIdx(s, x) - FirstIdx(s, x) + 1; } void Clear(ordered_set &s) { // this function clears all the elements from the set. s.clear(); } int Size(ordered_set &s) { // this function returns the size of the set. return (int)(s.size()); } vector<int> dijkstra(int start, int N) { vector<int> dist(N, 1e18); priority_queue<pi, vector<pi>, greater<pi>> q; q.push({0, start}); dist[start] = 0; int node, weight; while (q.size()) { node = q.top().ss; q.pop(); for (auto i : graph[node]) { if (dist[i.ss] > dist[node] + i.ff) { dist[i.ss] = dist[node] + i.ff; q.push({dist[i.ss], i.ss}); } } } return dist; } void solve() { int n, m; cin >> n >> m; int s, t, l, k; cin >> s >> t >> l >> k; int u, v, w; for (int i = 0; i < m; i++) { cin >> u >> v >> w; graph[u].push_back({w, v}); graph[v].push_back({w, u}); } vector<int> sdist = dijkstra(s, n + 1); vector<int> tdist = dijkstra(t, n + 1); if (sdist[t] <= k) { cout << n * (n - 1) / 2; return; } int ans1 = 0; int ans = 0; // cout << ans1 << endl; // cout << "------" << endl; // update(0, 1); ordered_set st; for (int i = 1; i <= n; i++) { if (tdist[i] <= 1e18) Insert(st, tdist[i]); // cout << tdist[i] << " "; } // cout << endl; // for (int i = 1; i <= n; i++) // { // cout << sdist[i] << " "; // } // cout << endl; // cout << query(0, 2) << endl; for (int i = 1; i <= n; i++) { // continue; if (tdist[i] < 1e18) Erase(st, tdist[i]); int kk = FirstIdx(st, k - l - sdist[i] + 1); ans += kk; // cout << "for " << i << " we have " << kk << endl; // cout << "ans = " << ans << endl; } Clear(st); for (int i = 1; i <= n; i++) { if (sdist[i] <= 1e18) Insert(st, sdist[i]); // cout << query(0, 1) << endl; } for (int i = 1; i <= n; i++) { // continue; if (sdist[i] < 1e18) Erase(st, sdist[i]); int kk = FirstIdx(st, k - l - tdist[i] + 1); ans += kk; // cout << "for " << i << " we have " << kk << endl; // cout << "ans = " << ans << endl; } cout << ans << endl; } signed main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int t = 1; // cin >> t; while (t--) { solve(); cout << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...