Avito Cool Challenge 2018 : D. Maximum Distance

pretestが弱かったようで。
https://codeforces.com/contest/1081/problem/D

問題

連結無向グラフが与えられる。
各辺にはコストが設定されている。
２頂点間の距離を、パス上の最大コストのうち、最適なパスを選んだ場合における最小値とする。

頂点のうち一部が特殊頂点であるものとする。
特殊頂点間のうち距離の最大値を求めよ。

解法

Union Findでコストの小さい順に辺を追加していき、特殊頂点が全部連結になった時点で終了すればよい。

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

int N,M,K;
int V[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,K) {
		cin>>x;
		V[x-1]=1;
	}
	
	vector<vector<int>> E;
	FOR(i,M) {
		cin>>x>>y>>r;
		E.push_back({r,x-1,y-1});
	}
	sort(ALL(E));
	
	FORR(e,E) {
		x=e[1];
		y=e[2];
		if(uf[x]!=uf[y]) {
			V[uf[x]]=V[uf[y]]=V[uf[x]]+V[uf[y]];
			uf(x,y);
			if(V[uf[x]]==K) {
				FOR(i,K) cout<<e[0]<<" ";
				return;
			}
		}
		
	}
	
	
	
}

まとめ

これはとくに迷わなかったな。