Submission #34687

---

Source Code Expand

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

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

struct edge{
	int u,v;
	ll cost;
	edge(){}
	edge(int u,int v,ll cost):u(u),v(v),cost(cost){}
	bool operator<(const edge &e)const{ return cost<e.cost; }
};

class union_find{
	vector<int> a;
public:
	union_find(int n):a(n,-1){}
	int find(int x){
		if(a[x]<0) return x;
		return a[x]=find(a[x]);
	}
	void unite(int x,int y){
		x=find(x),y=find(y);
		if(x!=y){ a[x]+=a[y]; a[y]=x; }
	}
	int size(int x){ return -a[find(x)]; }
};

ll Kruskal(int n,int m,edge *E){
	if(n<=1) return 0;

	ll tot=0;
	union_find U(n);
	sort(E,E+m);
	rep(i,m){
		if(U.find(E[i].u)!=U.find(E[i].v)){
			U.unite(E[i].u,E[i].v);
			tot+=E[i].cost;
			if(U.size(E[i].u)==n) return tot;
		}
	}
	return -1;
}

void construct(int n,int m,int E_[][3]){
	rep(i,n-1){
		int k=0;
		static edge E[200000];
		rep(j,m) if(E_[j][1]<i+2) E[k++]=edge(E_[j][0],E_[j][1],E_[j][2]);
		answer(Kruskal(i+2,k,E));
	}
}

Submission Info

Judge Result