Submission #1162574

#TimeUsernameProblemLanguageResultExecution timeMemory
1162574SyriusConstruction Project 2 (JOI24_ho_t2)C++20
0 / 100
3 ms4936 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ll long long #define ff first #define ss second #define pint pair < int , int > #define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL) typedef vector < int > vint; const int inf = 1e9 + 9; const int mxn = 2e5 + 2; const int mod = 1e9 + 7; int s , l , t , k , n , m; int dis[2][mxn]; vector < vector < pint > > adj(mxn); void build(int start , int id) { priority_queue < pint > q; q.push({0 , start}); while (!q.empty()) { pint p = q.top(); q.pop(); int u = p.ss; if (dis[id][u] != -1) continue; dis[id][u] = -p.ff; for (pint v : adj[u]) { q.push({p.ff - v.ss , v.ff}); } } } signed main() { cin >> n >> m; cin >> s >> t >> l >> k; for (int i = 0; i < m; i++) { int a , b , c; cin >> a >> b >> c; adj[a].push_back({b , c}); adj[b].push_back({a , c}); } for (int j = 0; j < 2; j++) { for (int i = 1; i <= n; i++) { dis[j][i] = -1; } } build(s , 0); build(t , 1); sort(dis[1] + 1 , dis[1] + 1 + n); if (dis[0][t] <= k && dis[0][t] != -1) { cout << n * (n - 1) / 2 << '\n'; return 0; } int ans = 0; for (int i = 1; i <= n; i++) { int L = 1 , R = n; while (L != R) { int M = (L + R) / 2; // cout << M << ' '; if (dis[1][M] + dis[0][i] + l <= k) L = M + 1; else R = M; } if (dis[1][R] + dis[0][i] + l <= k) ans++; // cout << R << '\n'; ans += R - 1; } cout << ans << '\n'; 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...