YEZAELP

TOI15: Budget

Oct 26th, 2021
625
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const int N = 3e3 + 10;
  6. const int P = 3e5 + 10;
  7. using pl = pair <lli, lli>;
  8. using pll = pair <lli, pl>;
  9. vector <pll> path;
  10. pl pack[P];
  11. lli parent[N];
  12.  
  13. lli root(lli u){
  14.     if(u == parent[u]) return u;
  15.     return parent[u] = root(parent[u]);
  16. }
  17.  
  18. void mrg(lli u, lli v){
  19.     u = root(u);
  20.     v = root(v);
  21.     if(u == v) return;
  22.     parent[v] = u;
  23. }
  24.  
  25. int main(){
  26.  
  27.     lli nnode, m;
  28.     scanf("%lld%lld", &nnode, &m);
  29.  
  30.     for(lli i=0;i<nnode;i++) parent[i] = i;
  31.  
  32.     for(lli i=1;i<=m;i++){
  33.         lli u, v, w, state;
  34.         scanf("%lld%lld%lld%lld", &u, &v, &w, &state);
  35.         if(state == 0) path.push_back({w, {u, v}});
  36.         else mrg(u, v);
  37.     }
  38.  
  39.     lli npack;
  40.     scanf("%lld", &npack);
  41.     for(lli i=1;i<=npack;i++){
  42.         lli l, p;
  43.         scanf("%lld%lld", &l, &p);
  44.         pack[i] = {l, p};
  45.     }
  46.  
  47.     sort(pack + 1, pack + npack + 1);
  48.     for(lli i=npack-1;i>=1;i--){
  49.         pack[i].second = min(pack[i].second, pack[i+1].second);
  50.     }
  51.  
  52.     lli len_path = path.size();
  53.     for(lli i=0;i<len_path;i++){
  54.         lli l = 1, r = npack, mn = npack;
  55.         while(l <= r){
  56.             lli mid = (l + r) / 2;
  57.             if(pack[mid].first >= path[i].first) r = mid - 1, mn = min(mn, mid);
  58.             else l = mid + 1;
  59.         }
  60.         path[i] = {pack[mn].second , {path[i].second.first, path[i].second.second}};
  61.     }
  62.  
  63.     sort(path.begin(), path.end());
  64.  
  65.     lli ans = 0;
  66.     for(lli i=0;i<len_path;i++){
  67.         lli w = path[i].first;
  68.         lli u = path[i].second.first;
  69.         lli v = path[i].second.second;
  70.         if(root(u) == root(v)) continue;
  71.         mrg(u, v);
  72.         ans += w;
  73.     }
  74.  
  75.     printf("%lld", ans);
  76.     return 0;
  77. }
  78.  
RAW Paste Data