#2109531

Solution for GRL_2_A: Minimum Spanning Tree by tuc_lt

Source Code Status Test Cases
    Policy: public     Reviewed: 5    
00.04 sec    8516 KB    110 lines     2014 bytes    2016-12-07 09:42
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;

struct UF {
  vector<int> par;
  vector<int> sizes;
  UF(int n) : par(n), sizes(n, 1) {
    rep(i,n) par[i] = i;
  }
  int root(int x) {
    if (x == par[x]) return x;
    return par[x] = root(par[x]);
  }
  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) {
      return;
    }
    if (sizes[x] < sizes[y]) {
      swap(x, y);
    }
    par[y] = x;
    sizes[x] += sizes[y];
    sizes[y] = 0;
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  int size(int x) {
    return sizes[root(x)];
  }
}; // UF

int V, E;
vvi edge;
ll cost;

void kruskal() {
  cost = 0;
  UF uf(V);
  rep (i, E) {
    auto e = edge[i];
    if (uf.same(e[1], e[2])) {
      continue;
    }
    uf.unite(e[1], e[2]);
    cost += e[0];
    if (uf.size(e[1]) == V) {
      break;
    }
  }
  return;
}

int main() {
  scanf("%d %d", &V, &E);
  edge.assign(E, vi(3));
  rep (i, E) {
    int s, t, w;
    scanf("%d %d %d", &s, &t, &w);
    edge[i][0] = w;
    edge[i][1] = s;
    edge[i][2] = t;
  }
  sort(all(edge));
  kruskal();
  printf("%lld\n", cost);

  return 0;
}


Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 20/20 C++14 CPU: 00.04 sec Memory: 8516 KB Length: 2014 B 2016-12-07 09:42 2016-12-07 09:42
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.00 sec 3212 KB
Case #2: : Accepted 00.00 sec 3132 KB
Case #3: : Accepted 00.00 sec 3080 KB
Case #4: : Accepted 00.00 sec 3492 KB
Case #5: : Accepted 00.02 sec 8400 KB
Case #6: : Accepted 00.00 sec 3132 KB
Case #7: : Accepted 00.04 sec 8372 KB
Case #8: : Accepted 00.01 sec 4544 KB
Case #9: : Accepted 00.01 sec 5756 KB
Case #10: : Accepted 00.02 sec 4964 KB
Case #11: : Accepted 00.01 sec 5380 KB
Case #12: : Accepted 00.01 sec 4804 KB
Case #13: : Accepted 00.00 sec 3176 KB
Case #14: : Accepted 00.00 sec 3100 KB
Case #15: : Accepted 00.00 sec 3208 KB
Case #16: : Accepted 00.00 sec 3100 KB
Case #17: : Accepted 00.04 sec 8504 KB
Case #18: : Accepted 00.03 sec 8372 KB
Case #19: : Accepted 00.04 sec 8372 KB
Case #20: : Accepted 00.04 sec 8516 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags