Submission #1189282

#TimeUsernameProblemLanguageResultExecution timeMemory
1189282guanexCommuter Pass (JOI18_commuter_pass)C++20
100 / 100
190 ms34712 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; //data structures typedef pair<ll, ll> ii; typedef vector<ii> vii; typedef vector<ll> vll; typedef vector<ld> vld; typedef pair<long long, long long> pll; typedef pair<char, ll> ci; typedef pair<string, ll> si; typedef vector<ll> vi; typedef vector<string> vs; typedef vector<vector<ll>> vvi; #define pb push_back #define pf push_front #define popb pop_back #define popf pop_front #define sz(a) ((ll)a.size()) #define fi first #define se second #define whole(v) v.begin(), v.end() #define rwhole(v) v.rbegin(), v.rend() #define fro front #define pqueue priority_queue #define ubound upper_bound #define lbound lower_bound #define beg(v) v.begin() //bit operations ll flip(ll x){ return ~(x) ^ (1 << 32); } ll allon(ll x){ return (1LL << x) - 1; } bool bit(ll a, ll i){ return (1LL << i) & a; } #define llpc(x) __builtin_popcountll(x) #define ipc(x) __builtin_popcount(x) #define iclz(x) __builtin_clz(x) #define llclz(x) __builtin_clzll(x) #define ictz(x) __builtin_ctz(x) #define llctz(x) __builtin_ctzll(x) //answers #define cYES cout << "YES" << endl #define cYes cout << "Yes" << endl #define cyes cout << "yes" << endl #define cNO cout << "NO" << endl #define cNo cout << "No" << endl #define cno cout << "no" << endl #define ipsb cout << -1 << endl const ll mod2 = 998244353; const ll mod = 1000000007; const ll inf = ll(1e18); // read arr vec matr etc #define fill(x, y) memset(x, y, sizeof(x)) void read(vector<auto> &x){ for(auto &e:x) cin >> e; } void mread(vector<vector<ll>> &p, ll nnn, ll mmm){ for(ll i = 0; i < nnn; ++i){ vector<ll> pp; for(ll j = 0; j < mmm; ++j){ ll wq; cin >> wq; pp.pb(wq); } p.pb(pp); } } // Solution int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n, m; cin >> n >> m; ll s, t; cin >> s >> t; ll a, b; cin >> a >> b; vector<vii> x(n+1); for(ll i = 0; i < m; ++i){ ll u, v; cin >> u >> v; ll cost; cin >> cost; x[u].pb({v, cost}); x[v].pb({u, cost}); } ll pass[n+1]; ll dist[n+1]; ll dis[n+1]; for(ll i = 0; i <= n; ++i){ dis[i] = inf; dist[i] = inf; pass[i] = inf; } pqueue<pair<ll, ii>, vector<pair<ll, ii>>, greater<pair<ll, ii>>> q; q.push({0, {s, s}}); pass[s] = 0; ll fat[n+1]; vvi child(n+1); vvi fats(n+1); fill(fat, 0); int vi[n+1]; fill(vi, 0); while(sz(q)){ ll no = q.top().se.se; ll fa = q.top().se.fi; ll cost = q.top().fi; q.pop(); if(pass[no] != cost){ continue; } fat[no]++; fats[no].pb(fa); if(vi[no])continue; vi[no] = 1; for(auto e:x[no]){ ll ncost = cost + e.se; if(pass[e.fi] >= ncost){ pass[e.fi] = ncost; q.push({ncost, {no, e.fi}}); } } } queue<ll> bfs; bfs.push(t); while(sz(bfs)){ ll no = bfs.fro(); bfs.pop(); if(vi[no] == 3)continue; vi[no] = 3; for(auto e:fats[no]){ child[e].pb(no); if(vi[e] <= 1){ vi[e] = 2; bfs.push(e); } } } pqueue<ii, vii, greater<ii>> pq; pq.push({0, a}); dist[a] = 0; while(sz(pq)){ ll no = pq.top().se; ll cost = pq.top().fi; pq.pop(); if(dist[no] != cost){ continue; } for(auto e:x[no]){ ll ncost = cost + e.se; if(ncost < dist[e.fi]){ dist[e.fi] = ncost; pq.push({ncost, e.fi}); } } } //cout << "work" << endl; pq.push({0, b}); dis[b] = 0; while(sz(pq)){ ll no = pq.top().se; ll cost = pq.top().fi; pq.pop(); if(dis[no] != cost){ continue; } for(auto e:x[no]){ ll ncost = cost + e.se; if(ncost < dis[e.fi]){ dis[e.fi] = ncost; pq.push({ncost, e.fi}); } } } ll ans = dist[b]; ll dpa[n+1]; ll dpb[n+1]; ll dpma[n+1]; ll dpmb[n+1]; for(ll i = 0; i <= n; ++i){ dpa[i] = inf; dpb[i] = inf; dpma[i] = inf; dpmb[i] = inf; } bfs.push(s); dpa[s] = dist[s]; dpb[s] = dis[s]; dpma[s] = dpa[s]; dpmb[s] = dpb[s]; ll vis[n+1]; fill(vis, 0); while(sz(bfs)){ ll no = bfs.fro(); bfs.pop(); if(vis[no]){ continue; } vis[no] = 1; for(auto e:child[no]){ fat[e]--; if(fat[e] == 0){ bfs.push(e); } } ll newa = dist[no]; ll newb = dis[no]; ll an = newa + newb; dpa[no] = newa; dpb[no] = newb; dpma[no] = dpa[no]; dpmb[no] = dpb[no]; for(auto e:fats[no]){ dpma[no] = min(dpma[no], dpma[e]); dpmb[no] = min(dpmb[no], dpmb[e]); ll nan = inf; nan = min(nan, dpma[no] + newb); if(nan < an){ dpa[no] = dpma[no]; dpb[no] = newb; an = nan; } nan = min(nan, dpmb[no] + newa); if(nan < an){ dpa[no] = newa; dpb[no] = dpmb[no]; an = nan; } } } for(ll i = 0; i <= n; ++i){ ans = min(ans, dpa[i] + dpb[i]); //cout << ans << " " << i << endl; } cout << ans << endl; }

Compilation message (stderr)

commuter_pass.cpp: In function 'll flip(ll)':
commuter_pass.cpp:38:22: warning: left shift count >= width of type [-Wshift-count-overflow]
   38 |     return ~(x) ^ (1 << 32);
      |                    ~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...