問題ネタが少ないのかなぁ…
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"; } }
まとめ
なぜミスった。