Submission #1112298

#TimeUsernameProblemLanguageResultExecution timeMemory
1112298Mike_VuConstruction Project 2 (JOI24_ho_t2)C++14
100 / 100
199 ms24584 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double dou; #define pii pair<int, int> #define fi first #define se second #define pb push_back #define MASK(x) (1LL<<(x)) #define BITj(x, j) (((x)>>(j))&1) template<typename T> bool maximize(T &x, const T &y) { if (x < y) {x = y; return 1;} return 0; } template<typename T> bool minimize(T &x, const T &y) { if (x > y) {x = y; return 1;} return 0; } const int maxn = 2e5+5; int n, m, s, t; ll len, bound, ans = 0; vector<pii> a[maxn]; ll dis1[maxn], dis2[maxn]; void dijkstra(int s, ll dis[]) { priority_queue<pair<ll, int>> q; q.push({0, s}); dis[s] = 0; while (!q.empty()) { int u = q.top().se; ll w = -q.top().fi; q.pop(); if (w != dis[u]) continue; for (int i = 0; i < (int)a[u].size(); i++) { int v = a[u][i].fi, w = a[u][i].se; if (minimize(dis[v], dis[u]+w)) { q.push({-dis[v], v}); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); // #define name "task" // if (fopen(name".inp", "r")) { // freopen(name".inp", "r", stdin); // freopen(name".out", "w", stdout); // } cin >> n >> m >> s >> t >> len >> bound; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; a[u].pb({v, w}); a[v].pb({u, w}); } //dijkstra memset(dis1, 0x3f, sizeof(dis1)); dijkstra(s, dis1); memset(dis2, 0x3f, sizeof(dis2)); dijkstra(t, dis2); //check case 1 if (dis1[t] <= bound) { cout << ((ll)n*(n-1)/2); return 0; } //cal + bs vector<pair<ll, int>> val; for (int i = 1; i <= n; i++) { val.pb({dis1[i], i}); } sort(val.begin(), val.end()); for (int i = 1; i < n; i++) { int u = val[i].se; //binsearch with bound ll curbound = bound-len-dis2[u]; if (curbound < 0) continue; int k = -1; for (int j = n>>1; j; j >>= 1) { while (k+j < n && val[k+j].fi <= curbound) k += j; } ans += k+1; } //output cout << ans; } /* 7 8 6 7 1 2 1 2 1 1 6 1 2 3 1 2 4 1 3 5 1 3 7 1 4 5 1 5 6 1 3 2 1 3 1 2 1 2 1 2 3 1 6 4 2 5 1000000000 1 1 2 1000000000 2 3 1000000000 2 4 1000000000 5 6 1000000000 18 21 4 8 678730772 3000000062 5 13 805281073 8 17 80983648 3 8 996533440 10 16 514277428 2 5 57914340 6 11 966149890 8 12 532734310 2 9 188599710 2 3 966306014 12 16 656457780 16 18 662633078 1 15 698078877 2 8 665665772 2 6 652261981 14 15 712798281 7 13 571169114 13 14 860543313 6 7 454251187 9 14 293590683 6 14 959532841 3 11 591245645 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...