fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define debug     cout << "ok\n";
  4. #define SQR(x)    (1LL * ((x) * (x)))
  5. #define MASK(i)   (1LL << (i))
  6. #define BIT(x, i) (((x) >> (i)) & 1)
  7. #define fi        first
  8. #define se        second
  9. #define pb        push_back
  10.  
  11. #define mp make_pair
  12. #define pii pair<int, int>
  13. #define pll pair<ll, ll>
  14. #define pli pair<ll, int>
  15. #define vi vector<int>
  16. #define vll vector<ll>
  17.  
  18. #define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef long double ld;
  23. typedef unsigned int ui;
  24.  
  25. using namespace std;
  26.  
  27. const int M = 1e9 + 7;
  28. const int INF = 1e9 + 7;
  29. const ll INFLL = (ll)2e18 + 7LL;
  30. const ld PI = acos(-1);
  31.  
  32. const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
  33. const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
  34.  
  35. template<class _, class __>
  36.     bool minimize(_ &x, const __ y){
  37.         if(x > y){
  38.             x = y;
  39.             return true;
  40.         } else return false;
  41.     }
  42. template<class _, class __>
  43.     bool maximize(_ &x, const __ y){
  44.         if(x < y){
  45.             x = y;
  46.             return true;
  47.         } else return false;
  48.     }
  49.  
  50. //--------------------------------------------------------------
  51.  
  52. const int MaxN = 1e6+7;
  53.  
  54. int n1,m1,n2,m2;
  55. ll res = 0;
  56.  
  57. struct Edges {
  58.     int u;
  59.     int v;
  60.     int w;
  61.     bool side;
  62. } edge[MaxN];
  63.  
  64. bool cmp(Edges a,Edges b) {
  65.     return a.w < b.w;
  66. }
  67.  
  68. struct DSU {
  69.     vi lab;
  70.     int n,tplt;
  71.  
  72.     DSU(int _n) {
  73.         n = _n;
  74.         lab.assign(_n+1,-1);
  75.         tplt = n;
  76.     }
  77.  
  78.     int GR(int u) {
  79.         return lab[u] < 0 ? u : lab[u] = GR(lab[u]);
  80.     }
  81.  
  82.     bool add_edges(Edges _edge) {
  83.         int r1 = GR(_edge.u);
  84.         int r2 = GR(_edge.v);
  85.         if (r1 == r2) return false;
  86.         if (lab[r1] < lab[r2]) {
  87.             lab[r1] += lab[r2];
  88.             lab[r2] = r1;
  89.         }
  90.         else {
  91.             lab[r2] += lab[r1];
  92.             lab[r1] = r2;
  93.         }
  94.         tplt--;
  95.         return true;
  96.     }
  97. };
  98.  
  99. void sol() {
  100.     cin >> n1 >> m1;
  101.     for (int i=1;i<=m1;i++) {
  102.         int u,v,w;
  103.         cin >> u >> v >> w;
  104.         edge[i] = (Edges){u,v,w,0};
  105.     }
  106.     cin >> n2 >> m2;
  107.     for (int i=1;i<=m2;i++) {
  108.         int u,v,w;
  109.         cin >> u >> v >> w;
  110.         edge[i+m1] = (Edges){u,v,w,1};
  111.     }
  112.     sort(edge+1,edge+m1+m2+1,cmp);
  113.     DSU dsu1(n1);
  114.     DSU dsu2(n2);
  115.     for (int i=1;i<=m1+m2;i++) {
  116.         if (edge[i].side) {
  117.             if (dsu2.add_edges(edge[i])) {
  118.                 res += 1LL*dsu1.tplt*edge[i].w;
  119.             }
  120.         }
  121.         else {
  122.             if (dsu1.add_edges(edge[i])) {
  123.                 res += 1LL*dsu2.tplt*edge[i].w;
  124.             }
  125.         }
  126.     }
  127.     cout << res;
  128. }
  129.  
  130. int main() {
  131. //	freopen("TWOGRAPH.inp","r",stdin);
  132. //	freopen("TWOGRAPH.out","w",stdout);
  133. 	FAST
  134. 	int t=1;
  135. //	cin >> t;
  136. 	while (t--) sol();
  137. }
  138.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/r63953
language:
C++14 (gcc 8.3)
created:
17 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!