TopCoder SRM 716 Div1 Medium JumpDistancesOnTree、Div2 Hard JumpDistancesOnTreeEasy

問題ネタが少ないのかなぁ…
https://community.topcoder.com/stat?c=problem_statement&pm=14625
https://community.topcoder.com/stat?c=problem_statement&pm=14626

問題

木を成すグラフが与えられる。
各辺の長さはいずれも1である。

頂点0から初めて、何度か頂点間をジャンプしたとする。
毎回のジャンプ前後の頂点間の距離を並べた配列をDとし、さらにそれを集合に落としたものをSとする。
Sが与えられたとき、それを満たす移動順は存在するか判定せよ。

解法

Sに含まれる距離のジャンプは最低1回は必要で、以後何回行ってもよい。
そこで、まず後者の条件に基づき頂点0から移動可能な頂点を列挙しよう。

あとは移動可能な頂点対の距離で、Sの各要素が1回以上含まれるかを判定すればよい。

int N;
vector<int> E[2020];
vector<int> D[2020][2020];
int dist[2020][2020];

class JumpDistancesOnTree {
	public:
	void dfs(int cur,int pre,int base,int d) {
		dist[base][cur]=d;
		D[base][d].push_back(cur);
		FORR(e,E[cur]) if(e!=pre) dfs(e,cur,base,d+1);
	}
	
	string isPossible(vector <int> p, vector <int> S) {
		int i,x,y;
		N=p.size()+1;
		FOR(i,N) E[i].clear();
		FOR(x,N) FOR(y,N) D[x][y].clear();
		FOR(i,p.size()) {
			E[i+1].push_back(p[i]);
			E[p[i]].push_back(i+1);
		}
		
		FOR(i,N) dfs(i,i,i,0);
		
		bitset<2020> A;
		A[0]=1;
		queue<int> Q;
		Q.push(0);
		while(Q.size()) {
			int cur=Q.front();
			Q.pop();
			FORR(d,S) FORR(e,D[cur][d]) if(A[e]==0) {
				A[e]=1;
				Q.push(e);
			}
		}
		
		set<int> T;
		FORR(r,S) T.insert(r);
		
		FOR(x,N) FOR(y,N) if(A[x]&&A[y]) T.erase(dist[x][y]);
		
		if(T.empty()) return "Possible";
		return "Impossible";
	}
}

まとめ

なぜミスった。