Submission #35205

---

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,cost;
	edge(){}
	edge(int u,int v,int 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)]; }
};

void construct(int n,int m,int E_[][3]){
	static vector<edge> E[200000]; // E[v] := ( 番号が大きい方の端点が v である辺の集合 )
	rep(i,m) E[E_[i][1]].push_back(edge(E_[i][0],E_[i][1],E_[i][2]));

	vector<edge> F;
	for(int k=2;k<=n;k++){
		F.insert(F.end(),E[k-1].begin(),E[k-1].end());
		sort(F.begin(),F.end());

		ll ans=0;
		int cnt=0;
		union_find U(k);
		vector<bool> used(F.size());
		rep(i,F.size()){
			int u=F[i].u,v=F[i].v,cost=F[i].cost;

			if(U.find(u)!=U.find(v)){
				U.unite(u,v);
				ans+=cost;
				cnt++;
				used[i]=true;
			}
		}
		answer(cnt==k-1?ans:-1);

		vector<edge> tmp=F;
		F.clear();
		rep(i,used.size()) if(used[i]) F.push_back(tmp[i]);
	}
}

Submission Info

Judge Result