Submission #1217452

#TimeUsernameProblemLanguageResultExecution timeMemory
1217452baojiaopisuConstruction Project 2 (JOI24_ho_t2)C++20
0 / 100
51 ms18872 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using pii = pair<int, int>; using pll = pair<long long, long long>; #define pb push_back #define ins insert #define fi first #define se second #define btpc __builtin_popcount #define btclz __builtin_clz #define sz(x) (int)(x.size()); #define all(x) x.begin(), x.end() #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1}; int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1}; int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1}; template<class X, class Y> bool minimize(X &x, const Y &y) { if (x > y) { x = y; return true; } return false; } template<class X, class Y> bool maximize(X &x, const Y &y) { if (x < y) { x = y; return true; } return false; } const int MOD = 1e9 + 7; //998244353 /* Author : Le Ngoc Bao Anh, A5K37 Le Quy Don High School for Gifted Student, Da Nang */ /* University of Wollongong */ const long long INF = 1e9; const int N = 2e5 + 10; vector<pll> adj[N]; void BaoJiaoPisu() { int n, m; cin >> n >> m; ll S, T, L, K; cin >> S >> T >> L >> K; for(int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; adj[u].pb({v, w}); adj[v].pb({u, w}); } auto F = [&](int S) -> vector<ll> { vector<ll> dist(n + 1, INF * INF); dist[S] = 0; struct PQ { int u; ll w; bool operator < (const PQ & temp) const { return w > temp.w; } }; priority_queue<PQ> q; q.push({S, 0}); while(q.size()) { PQ T = q.top(); q.pop(); int u = T.u; if(T.w != dist[u]) continue; for(auto nxt : adj[u]) { int v = nxt.fi; ll w = nxt.se; if(minimize(dist[v], dist[u] + w)) q.push({v, dist[v]}); } } return dist; }; vector<ll> distS = F(S); vector<ll> distT = F(T); if(distS[T] <= K) { cout << 1ll * n * (n - 1) / 2; return; } ll ans = 0; sort(all(distT)); for(int i = 0; i < n; i++) { int pos = -1; int l = 0, r = n - 1; while(l <= r) { int mid = (l + r) >> 1; if(distS[i] + distT[mid] + L <= K) { pos = mid; l = mid + 1; } else { r = mid - 1; } } ans += pos + 1; } cout << ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifndef ONLINE_JUDGE #else //online #endif int tc = 1, ddd = 0; // cin >> tc; while(tc--) { //ddd++; //cout << "Case #" << ddd << ": "; BaoJiaoPisu(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...