Submission #1187318

#TimeUsernameProblemLanguageResultExecution timeMemory
1187318Zbyszek99Construction Project 2 (JOI24_ho_t2)C++20
100 / 100
366 ms31204 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<pair<long long,long long>, null_type, less<pair<long long,long long>>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; ll dist[200'001][2]; vector<pll> graph[200'001]; int n,m,s,t; ll L,K; void dij(int start, int type) { rep2(i,1,n) dist[i][type] = 1e18; priority_queue<pll,vector<pll>,greater<pll>> pq; pq.push({0,start}); while(!pq.empty()) { pll t = pq.top(); pq.pop(); if(dist[t.ss][type] != 1e18) continue; dist[t.ss][type] = t.ff; forall(it,graph[t.ss]) { pq.push({t.ff+it.ss,it.ff}); } } } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); cin >> n >> m >> s >> t >> L >> K; rep(i,m) { int a,b,c; cin >> a >> b >> c; graph[a].pb({b,c}); graph[b].pb({a,c}); } dij(s,0); dij(t,1); if(dist[t][0] <= K) { cout << ((ll)n * (ll)(n-1)) / 2 << "\n"; return 0; } ll ans = 0; ordered_set dists; rep2(i,1,n) { auto it = dists.upper_bound({K - (dist[i][0] + L),1e9}); if(it != dists.begin()) { it--; ans += dists.order_of_key(*it)+1; } dists.insert({dist[i][1],i}); } dists = {}; rep2(i,1,n) { auto it = dists.upper_bound({K - (dist[i][1] + L),1e9}); if(it != dists.begin()) { it--; ans += dists.order_of_key(*it)+1; } dists.insert({dist[i][0],i}); } cout << ans << "\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...