TopCoderOpen 2016 Round1A Hard EllysTree

少し手こずったけど一応自力で解けた。
https://community.topcoder.com/stat?c=problem_statement&pm=12395

問題

0番の頂点を根とする、0～N番の(N+1)頂点からなる木を成すグラフが与えられる。
このグラフ上で、0番の頂点から初めて、全頂点をちょうど1回ずつ通りたい。
頂点間の移動は、移動元と先が祖先と子孫の関係にあるなら1手で移動できる。

与えられた木とルールにおいて、全頂点を1回ずつたどる移動は可能か。
可能なら頂点の訪問順が辞書順最小となるものを求めよ。

解法

辞書順の定番テクで解く。
今頂点xにいる場合、xから移動可能かつ未訪問の頂点のうち、番号の小さい順に
「その頂点yに移動した場合、最終的に全頂点が訪問可能か」
を判定すればよい。

カギ括弧内の判定は訪問可否を問うだけで順序を問わないので、元々の問題よりずっと判定は容易である。
これは以下の要領で貪欲に次の頂点を辿っていけば良い。

• 今いる頂点から移動可能な未訪問頂点のうち、最も深い頂点を選ぶ(子孫でも先祖でもよい)

int mat[105][105];
int did[1010];

class EllysTree {
	public:
	
	int N;
	int ok(int st,int L) {
		int did2[101];
		int i,j;
		FOR(i,N) did2[i]=did[i];
		did2[st]=1;
		
		FOR(i,L) {
			int be=-1;
			FOR(j,N) if(did2[j]==0 && (mat[st][j]<=100 || mat[j][st]<=100)) {
				if(be==-1 || mat[0][be]<mat[0][j]) be=j;
			}
			if(be==-1) return 0;
			st=be;
			did2[st]=1;
		}
		return 1;
	}
	
	vector <int> getMoves(vector <int> parent) {
		int i,x,y,z;
		N=parent.size()+1;
		FOR(x,N) FOR(y,N) mat[x][y]=(x!=y)*1010;
		FOR(i,N-1) mat[parent[i]][i+1]=1;
		FOR(z,N) FOR(x,N) FOR(y,N) mat[x][y] = min(mat[x][y],mat[x][z]+mat[z][y]);
		
		vector<int> V;
		ZERO(did);
		did[0]=1;
		x = 0;
		while(1) {
			FOR(i,N) if(did[i]==0 && (mat[x][i]<=100 || mat[i][x]<=100) && ok(i,N-2-V.size())) {
				did[i]=1;
				x=i;
				V.push_back(i);
				break;
			}
			if(i==N) break;
		}
		
		
		if(V.size()!=N-1) V.clear();
		return V;
		
	}
}

まとめ

これ計算量どの位だろ。O(N^3)？