fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  3. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  4. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  5. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  6. #define ll long long
  7. #define el "\n"
  8. #define fi first
  9. #define se second
  10. #define _ROOT_ int main()
  11. #define M 1000000007
  12. #define MAXN 1000001
  13. #define INF (1ll<<60)
  14. #define NAME "file"
  15. #define debug(a) cout << #a << " = " << a << endl;
  16. using namespace std;
  17.  
  18. ll n, m, q, m_1, m_2, s, t, ans = INF ;
  19. ll a[MAXN] ;
  20. ll lab[MAXN ] ;
  21.  
  22. struct Edge {
  23.     ll u, v, w ;
  24.     bool operator < (const Edge & other ) const {
  25.         return w < other.w ;
  26.     }
  27. };
  28. Edge A[MAXN], B[MAXN ] ;
  29.  
  30. struct Data {
  31.     ll u, v, sz_u, sz_v ;
  32. };
  33. stack<Data> history ;
  34.  
  35. ll find_set(ll a ) {
  36.     return lab[a] < 0 ? a : find_set(lab[a]) ;
  37. }
  38. ll same_set(ll a, ll b ) {
  39.     return find_set(a) == find_set(b) ;
  40. }
  41. bool union_set(ll a, ll b ) {
  42.     a = find_set(a) ;
  43.     b = find_set(b) ;
  44.     if(a == b ) return false ;
  45.     if(lab[a] > lab[b]) swap(a, b ) ;
  46.     history.push({a, b, lab[a], lab[b] }) ;
  47.     lab[a] += lab[b] ;
  48.     lab[b] = a;
  49.     return true ;
  50. }
  51.  
  52. ll snapshot() {
  53.     return history.size() ;
  54. }
  55.  
  56. void rollBack(ll time ) {
  57.     while(history.size() > time ) {
  58.         Data u = history.top() ;
  59.         lab[u.u] = u.sz_u ;
  60.         lab[u.v] = u.sz_v ;
  61.         history.pop() ;
  62.     }
  63. }
  64.  
  65. void dnc(ll l1, ll r1, ll l2, ll r2 ) {
  66.     if(l1 > r1 || l2 > r2 ) return ;
  67.     ll snap = snapshot() ;
  68.     ll mid = l1 + r1 >> 1 ;
  69.     FOR(i, l1, mid ) union_set(A[i].u, A[i].v ) ;
  70.     ll fmid = -1 ;
  71.     FOR(i, l2, r2 ) {
  72.         union_set(B[i].u, B[i].v ) ;
  73.         if(same_set(s, t )) {
  74.             fmid = i ;
  75.             break ;
  76.         }
  77.     }
  78.  
  79.     if(fmid != -1 ) {
  80.         ans = min(ans, B[fmid].w + A[mid].w ) ;
  81.     }
  82.     rollBack(snap ) ;
  83.     if(l1 == r1 ) return ;
  84.  
  85.     FOR(i, l1, mid ) union_set(A[i].u, A[i].v ) ;
  86.  
  87.     if(fmid == -1 ) {
  88.         dnc(mid + 1, r1, l2, r2 ) ;
  89.     } else {
  90.         dnc(mid + 1, r1, l2, fmid ) ;
  91.     }
  92.     rollBack(snap ) ;
  93.  
  94.     if(fmid != -1 ) {
  95.         FOR(i, l2, fmid - 1 ) union_set(B[i].u, B[i].v ) ;
  96.         dnc(l1, mid, fmid, r2 ) ;
  97.         rollBack(snap ) ;
  98.     }
  99. }
  100.  
  101. void init() {
  102.     cin >> n >> m >> s >> t ;
  103.     FOR(i, 1, m ) {
  104.         ll t, u, v, w ;
  105.         cin >> t >> u >> v >> w ;
  106.         if(t == 1 ) {
  107.             m_1 ++ ;
  108.             A[m_1] = {u, v, w } ;
  109.         } else {
  110.             m_2 ++ ;
  111.             B[m_2] = {u, v, w } ;
  112.         }
  113.     }
  114.     sort(A + 1, A + m_1 + 1 ) ;
  115.     sort(B + 1, B + m_2 + 1 ) ;
  116. }
  117.  
  118. void solve() {
  119.     memset(lab, -1, sizeof lab ) ;
  120.  
  121.     FOR(i, 1, m_2 ) {
  122.         union_set(B[i].u, B[i].v ) ;
  123.         if(same_set(s, t )) {
  124.             ans = min(B[i].w , ans ) ;
  125.             break ;
  126.         }
  127.     }
  128.     rollBack(0) ;
  129.     FOR(i, 1, m_1 ) {
  130.         union_set(A[i].u, A[i].v ) ;
  131.         if(same_set(s, t )) {
  132.             ans = min(A[i].w , ans ) ;
  133.             break ;
  134.         }
  135.     }
  136.     rollBack(0) ;
  137.     dnc(1, m_1, 1, m_2 ) ;
  138.     cout << ans << el ;
  139. }
  140.  
  141. _ROOT_ {
  142.     // freopen(NAME".inp" , "r" , stdin);
  143.     // freopen(NAME".out" , "w", stdout) ;
  144.     ios_base::sync_with_stdio(0);
  145.     cin.tie(0);
  146.     cout.tie(0);
  147.     int t = 1; // cin >> t ;
  148.     while(t--) {
  149.         init();
  150.         solve();
  151.     }
  152.     return (0&0);
  153. }
  154.  
Success #stdin #stdout 0.01s 13808KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1152921504606846976
https://ideone.com/yf1Gcb
language:
C++14 (gcc 8.3)
created:
19 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!