Codeforces Global Round 21 : F. Tree Recovery

GCJみたいなテストケース構成だな…。
https://codeforces.com/contest/1696/problem/F

問題

N頂点からなる木を成す無向グラフがある。
3点x,y,zに対し、dist(x,z)=dist(y,z)であるかどうかが与えられる。
条件を満たす木が存在するか判定し、存在するなら1例を示せ。

解法

2頂点の対はC(N,2)通りあるが、この対を頂点とする別のグラフを考える。
dist(x,z)==dist(y,z)なら、(x,z)と(y,z)に対応する点の間に辺を張る。

このグラフは、元グラフが木なら(N-1)要素の連結成分を持つ。
その(N-1)個の点(元グラフの(N-1)本の辺)が、入力の条件を満たすか判定してみるとよい。

int T;
int N;
int M[101][101][101];
int E[101][101];
int ok;
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 num=um) {int i; FOR(i,num) 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<10101> uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		uf.reinit(N*N);
		cin>>N;
		ZERO(M);
		ZERO(E);
		FOR(i,N) {
			for(j=1;i+j<N;j++) {
				cin>>s;
				FOR(k,N) {
					M[i][i+j][k]=s[k]-'0';
					if(s[k]=='1') uf(min(i,k)*N+max(i,k),min(i+j,k)*N+max(i+j,k));
				}
			}
		}
		vector<pair<int,int>> Es;
		
		FOR(y,N) FOR(x,y) if(uf[x*N+y]==x*N+y&&uf.count(x*N+y)==N-1) {
			FOR(i,N) FOR(j,N) E[i][j]=(i==j)?0:1010;
			FOR(j,N) FOR(i,j) if(uf[i*N+j]==x*N+y) E[i][j]=E[j][i]=1;
			FOR(k,N) FOR(i,N) FOR(j,N) E[i][j]=min(E[i][j],E[i][k]+E[j][k]);
			int ok=1;
			FOR(j,N) FOR(i,j) FOR(k,N) if((E[i][k]==E[j][k])!=M[i][j][k]) ok=0;
			if(ok==1) {
				Es.clear();
				FOR(j,N) FOR(i,j) if(uf[i*N+j]==x*N+y) Es.push_back({i+1,j+1});
			}
		}
		
		if(Es.size()) {
			cout<<"Yes"<<endl;
			FORR2(a,b,Es) cout<<a<<" "<<b<<endl;
		}
		else {
			cout<<"No"<<endl;
		}
	}
}

まとめ

うーん、本番で思いつける気がしないな。