Submission #1182756

#TimeUsernameProblemLanguageResultExecution timeMemory
1182756DedibeatConstruction Project 2 (JOI24_ho_t2)C++20
0 / 100
5 ms5192 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; #define F first #define S second #define all(x) (x).begin(), (x).end() template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) { return os << "(" << p.F << "," << p.S << ")"; } template<typename T> void print(const T &v, int lim = 1e9) { for(auto x : v) if(lim-- > 0) cout << x << " "; cout << "\n"; } #define int long long int N, M, S, T, L, K; using node = pair<ll, ll>; vector<node> adj[200005]; struct Node { ll val; // Value of the segment (e.g., sum) Node *left; // Left child Node *right; // Right child aa Node() : val(0), left(nullptr), right(nullptr) {} }; class DynamicSegmentTree { private: Node* root; ll l_bound, r_bound; void update(Node*& node, ll l, ll r, ll idx, ll value) { if (!node) node = new Node(); if (l == r) { node->val += value; return; } ll mid = l + (r - l) / 2; if (idx <= mid) { update(node->left, l, mid, idx, value); } else { update(node->right, mid + 1, r, idx, value); } node->val = getValue(node->left) + getValue(node->right); } ll query(Node* node, ll l, ll r, ll ql, ll qr) { if (!node || ql > r || qr < l) return 0; if (ql <= l && r <= qr) { return node->val; } ll mid = l + (r - l) / 2; return query(node->left, l, mid, ql, qr) + query(node->right, mid + 1, r, ql, qr); } ll getValue(Node* node) { return node ? node->val : 0; } public: DynamicSegmentTree(ll l_bound, ll r_bound) : l_bound(l_bound), r_bound(r_bound), root(nullptr) {} void update(ll idx, ll value) { update(root, l_bound, r_bound, idx, value); } ll query(ll ql, ll qr) { return query(root, l_bound, r_bound, ql, qr); } }; signed main() { ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin >> N >> M >> S >> T >> L >> K; for(int i = 0; i < M; i++) { int u, v, w; cin >> u >> v >> w; adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); } auto dij = [&](int start) { priority_queue<node, vector<node> , greater<node>> q; vector<ll> d(N + 5, 1e17); d[start] = 0; q.emplace(0, start); while(!q.empty()) { auto [c, v] = q.top(); q.pop(); if(c != d[v]) continue; for(auto [u, w] : adj[v]) { if(c + w < d[u]) { d[u] = c + w; q.emplace(c + w, u); } } } return d; }; auto ds = dij(S); auto dt = dij(T); // print(ds); // print(dt); ll cnt = 0; vector<int> vert; for(int i = 1; i <= N; i++) vert.push_back(i); sort(vert.begin(), vert.end(), [&](int v, int u) { return ds[v] - dt[v] < ds[u] - dt[u]; }); DynamicSegmentTree st(0, 1e18); for(int v : vert) { // cout <<"node "<< v << " " << dt[v] << " " << ds[v] << endl; cnt += st.query(0, K - L - dt[v]); st.update(ds[v], 1); } cout << cnt << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...