fork download
copy 
  1. #include<bits/stdc++.h>
  2. #pragma GCC optimize("O3,unroll-loops")
  3. #define int long long
  4. #define maxn 1000005
  5. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. #define fi first
  7. #define se second
  8. #define ll long long
  9. #define sti string
  10.  
  11. using namespace std;
  12.  
  13. struct node {
  14.    int u,v,sz_u;
  15. };
  16.  
  17.  
  18.  
  19. struct DSU {
  20.    int n;
  21.    vector<int> par,sz;
  22.    vector<node> history;
  23.    DSU(int _n=0){
  24.       n=_n;
  25.       sz.assign(n+5,1);
  26.       par.assign(n+5,0);
  27.       for(int i=1;i<=n;i++) par[i]=i;
  28.    }
  29.    int find_par(int u){
  30.      while(u != par[u]){
  31.         u=par[u];
  32.      }
  33.      return u;
  34.    }
  35.    void join(int u,int v){
  36.      u=find_par(u);
  37.      v=find_par(v);
  38.      if(u==v){
  39.          history.push_back({-1,-1,0});
  40.          return ;
  41.      }
  42.      if(sz[u] < sz[v]) swap(u,v);
  43.      history.push_back({u,v,sz[u]});
  44.      sz[u]+=sz[v];
  45.      par[v]=u;
  46.    }
  47.    void rollback(int Time){
  48.       while(history.size() > Time){
  49.         auto [u,v,sz_u]=history.back();
  50.         history.pop_back();
  51.         if(v==-1) continue;
  52.         sz[u] = sz_u;
  53.         par[v]=v;
  54.       }
  55.    }
  56. };
  57.  
  58. DSU dsu;
  59. int s,t;
  60.  
  61. struct Edge {
  62.    int u,v,w;
  63.    bool operator < (const Edge &other) const {
  64.      return w < (other.w);
  65.    }
  66. };
  67.  
  68. vector<Edge> A,B;
  69. int n,m,q,res=4e18;
  70.  
  71.  
  72. void dnc(int LeftA,int RightA,int LeftB,int RightB){
  73.    if(LeftA  > RightA) return ;
  74.    int first = dsu.history.size();
  75.    int mid=(LeftA + RightA) /2;
  76.    for(int i = LeftA; i<=mid;i++){
  77.      dsu.join(A[i].u,A[i].v);
  78.    }
  79.    int pos = -1;
  80.    for(int j=LeftB;j<=RightB;j++){
  81.     if(dsu.find_par(s) == dsu.find_par(t)){
  82.         pos = j;
  83.         int costA = (mid >= 0 ) ? A[mid].w : 0;
  84.         int costB = (j>0) ? B[j-1].w : 0;
  85.         res = min(res, costA + costB);
  86.         break;
  87.     }
  88.     dsu.join(B[j].u,B[j].v);
  89.    }
  90.    if(pos == -1 && dsu.find_par(s) == dsu.find_par(t)){
  91.        pos = RightB + 1;
  92.        int costA = (mid >= 0 ) ? A[mid].w : 0;
  93.         int costB = (RightB>0) ? B[RightB].w : 0;
  94.         res = min(res, costA + costB);
  95.    }
  96.    dsu.rollback(first);
  97.  
  98.    if(pos == -1){
  99.       for(int j=LeftA;j<=RightA;j++) dsu.join(A[j].u,A[j].v);
  100.       dnc(mid+1,RightA,LeftB,RightB);
  101.       dsu.rollback(first);
  102.       return ;
  103.    }
  104.  
  105.    for(int j= LeftB;j < pos ; j++){
  106.      dsu.join(B[j].u,B[j].v);
  107.    }
  108.    dnc(LeftA,mid-1,pos,RightB);
  109.    dsu.rollback(first);
  110.  
  111.    for(int j=LeftA;j<=mid;j++) dsu.join(A[j].u,A[j].v);
  112.    dnc(mid+1,RightA,LeftB,pos);
  113.    dsu.rollback(first);
  114. }
  115.  
  116. signed main() {
  117.     itachi
  118.     cin>>n>>m>>s>>t;
  119.     for(int i=1;i<=m;i++){
  120.         int opt; cin>>opt;
  121.         int u,v,w;
  122.         cin>>u>>v>>w;
  123.         if(opt==1){
  124.             A.push_back({u,v,w});
  125.         }
  126.         else B.push_back({u,v,w});
  127.     }
  128.     sort(A.begin(),A.end());
  129.     sort(B.begin(),B.end());
  130.     dnc(0,(int)A.size()-1,0,(int)B.size()-1);
  131.     cout<<res;
  132.     return 0;
  133. }
  134.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4000000000000000000
https://ideone.com/sMLGaW
language:
C++14 (gcc 8.3)
created:
15 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!