Submission #77535

---

Source Code Expand

#include <vector>
#include <algorithm>
#include "grader.h"

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define fi first
#define se second
#define mp make_pair
#define pb push_back

typedef pair<int, int> P;
typedef long long ll;

vector<P> g[100010];

struct unionfind{
    int par[100010], rank[100010];

    void init(){
	rep(i, 100000){
	    par[i] = i;
	    rank[i] = 0;
	}
    }

    inline int find(int x){
	if(par[x] == x) return x;
	return par[x] = find(par[x]);
    }

    inline void unite(int x, int y){
	x = find(x), y = find(y);
	if(x == y) return ;
	if(rank[x] < rank[y]) par[x] = y;
	else {
	    par[y] = x;
	    rank[x] += (rank[x] == rank[y]);
	}
    }

    inline bool same(int a, int b){ return find(a) == find(b); }
}uf;

struct edge{
    int f, t, c;
    edge(int f, int t, int c) : f(f), t(t), c(c){}
    edge(){}
};

bool cmp(edge a, edge b){ return a.c < b.c; }

vector<edge> eg;

void construct(int n, int m, int e[][3]){
    rep(i, m) g[e[i][1]].pb(mp(e[i][0], e[i][2]));
    rep(i, n - 1){
	int v = i + 1;
	vector<edge> a;
	rep(j, g[v].size()){
	    eg.pb(edge(v, g[v][j].fi, g[v][j].se));
	}
	sort(eg.begin(), eg.end(), cmp);
	uf.init();
	int sz = v + 1;
	ll ans = 0;
	rep(j, eg.size()){
	    edge crt = eg[j];
	    if(uf.same(crt.f, crt.t)) continue;
	    a.pb(crt);
	    uf.unite(crt.f, crt.t);
	    --sz;
	    ans += crt.c;
	}
	eg = a;
	if(sz != 1){
	    answer(-1);
	}else{
	    answer(ans);
	}
    }
}

Submission Info

Judge Result