http://poj.org/problem?id=2114
蟻本と同じことやるだけ…と思うがO(MNlog^2N)になって通るわけないだろ!と思い、ググってみるとどうやらそれでいけるらしいと分かったので、submitしてみるとTLE。途方に暮れているとvectorにstaticつけると速くなるよって書いてあったのでつけてみると余裕でAC。わけわからん。
namespace CD { //centroid decomposition struct edge { int to, length; }; vector<edge> G[MAX_N]; bool centroid[MAX_N]; int subtree_size[MAX_N]; void init(int n) { rep(i, 0, n) G[i].clear(); } void add_edge(int a, int b, int c) { G[a].push_back((edge){b, c}); G[b].push_back((edge){a, c}); } int compute_subtree_size(int v, int p) { int c = 1; rep(i, 0, (int)G[v].size()) { int w = G[v][i].to; if(w == p || centroid[w]) continue; c += compute_subtree_size(G[v][i].to, v); } subtree_size[v] = c; return c; } pi search_centroid(int v, int p, int t) { pi res = pi(inf, -1); int s = 1, m = 0; rep(i, 0, (int)G[v].size()) { int w = G[v][i].to; if(w == p || centroid[w]) continue; MIN(res, search_centroid(w, v, t)); MAX(m, subtree_size[w]); s += subtree_size[w]; } MAX(m, t - s); MIN(res, pi(m, v)); return res; } void update(int s); bool solve_subproblem(int v) { if(ans > 0) return true; compute_subtree_size(v, -1); int s = search_centroid(v, -1, subtree_size[v]).sec; centroid[s] = true; rep(i, 0, (int)G[s].size()) { if(centroid[G[s][i].to]) continue; solve_subproblem(G[s][i].to); } update(s); centroid[s] = false; return ans > 0; } ////////////////////////////////////////////// edit from here //distance from centroid void enumerate_pathes(int v, int p, int d, vi &ds) { ds.push_back(d); rep(i, 0, (int)G[v].size()) { int w = G[v][i].to; if(w == p || centroid[w]) continue; enumerate_pathes(w, v, d + G[v][i].length, ds); } } //num of pairs whose lengths is less than k int count_pairs(vi &ds) { int res = 0; sort(ds.begin(), ds.end()); int j = (int)ds.size(); rep(i, 0, (int)ds.size()) { while(j > 0 && ds[i] + ds[j - 1] > K) j--; res += j - (j > i ? 1 : 0); } j = (int)ds.size(); rep(i, 0, (int)ds.size()) { while(j > 0 && ds[i] + ds[j - 1] >= K) j--; res -= j - (j > i ? 1 : 0); } return res; } void update(int s) { static vi ds; ds.clear(); ds.push_back(0); rep(i, 0, (int)G[s].size()) { if(centroid[G[s][i].to]) continue; static vi tds; tds.clear(); enumerate_pathes(G[s][i].to, s, G[s][i].length, tds); ans -= count_pairs(tds); ds.insert(ds.end(), tds.begin(), tds.end()); } ans += count_pairs(ds); } } int main() { while(true) { scanf("%d", &N); CD::init(N); if(N == 0) break; rep(i, 0, N) { while(true) { int a, b; scanf("%d", &a); if(a == 0) break; a--; scanf("%d", &b); CD::add_edge(i, a, b); } } while(true) { ans = 0; scanf("%d", &K); if(K == 0) break; if(CD::solve_subproblem(0)) printf("AYE\n"); else printf("NAY\n"); } printf(".\n"); } return 0; }
c++もっと詳しくならないとと思った。
