kmjp's blog

競技プログラミング参加記です

HackerRank University CodeSprint 5 : C. a,b Special Points

ライブラリバグで手間取ったけど何とか全完。
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結構頑張ったのになくなっちゃった…。