ライブラリバグで手間取ったけど何とか全完。
https://www.hackerrank.com/contests/university-codesprint-5/challenges/ab-special-points
問題
無向グラフが与えられる。
adj(v)を頂点vの隣接頂点数とする。
頂点vに対し、vから到達可能な頂点u,u'のうち a*adj(u) < adj(v) < b*adj(u') を満たすものがあるようなvはいくつあるか。
解法
連結成分毎に分割し、連結成分内のadj(v)の最小値と最大値を求めれば、あとは上記式を満たすかチェックするだけ。
template<int um> class UF { public: vector<int> par,rank; UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);} int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));} int operator()(int x,int y) { if((x=operator[](x))==(y=operator[](y))) return x; if(rank[x]>rank[y]) return par[x]=y; rank[x]+=rank[x]==rank[y]; return par[y]=x; } }; UF<500000> uf; int N,M,A,B; int E[303030]; vector<int> V[303030]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>A>>B; FOR(i,M) { cin>>x>>y; x--;y--; E[x]++; E[y]++; uf(x,y); } FOR(i,N) V[uf[i]].push_back(E[i]); int ret=0; FOR(i,N) if(V[i].size()) { sort(ALL(V[i])); FORR(v,V[i]) { if(v>1LL*V[i][0]*A && v<1LL*V[i].back()*B) ret++; } } cout<<ret<<endl; }
まとめ
D結構頑張ったのになくなっちゃった…。