FII Code Round #2 : D. Divided Kingdom

急に行われたこのコンテスト、なんなんだろうね。
https://csacademy.com/contest/fii-code-2019-round-2/task/divided-kingdom/

問題

距離付の辺をもつ無向グラフが与えられる。
頂点を2色で彩色したとき、同色の頂点対における最小距離を最大化せよ。

解法

グラフが二部グラフと仮定すると、ある頂点が2辺以上持つ場合、距離最小の2辺の和が解の候補になる。
まずこの値を計算しておこう。

次に、グラフを辺がない状態から初めて距離が短い順に辺を追加することを考える。
途中二部グラフでなくなってしまった場合、その辺は解の候補となるので先の2辺の長さの和と小さい方を答えよう。

int N,M;
vector<int> C[101010];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<201010> uf,uf2;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	set<vector<int>> S;
	FOR(i,M) {
		cin>>x>>y>>r;
		C[x-1].push_back(r);
		C[y-1].push_back(r);
		S.insert({r,x-1,y-1});
	}
	
	int mi=1<<30;
	FOR(i,N) if(C[i].size()>=2) {
		sort(ALL(C[i]));
		mi=min(mi,C[i][0]+C[i][1]);
	}
	if(mi==1<<30) return _P("-1\n");
	
	FORR(s,S) {
		if(uf[s[1]*2]==uf[s[2]*2]) {
			cout<<min(mi,s[0])<<endl;
			return;
		}
		uf(s[1]*2,s[2]*2+1);
		uf(s[2]*2,s[1]*2+1);
	}
	
	
	cout<<mi<<endl;
}

まとめ

これ自分で思いついたんだかEditorial見たんだか忘れてしまった。