BUET Inter-University Programming Contest - 2011 E, UVa-12428 : Enemy at the Gates

問題概要

ノード数N(<10^5)、辺数M(

解法

まず星グラフを考える。その後辺数が余っていたら頂点を一つ選んで既にあるクリークにその頂点を含むクリークになるように辺を追加する。First Acceptだったっぽい。

acceptされたコード

計算量O(sqrt(M))。

#include <cstdio>
using namespace std;

typedef long long int64;

int64 N, M;

void init(){
	scanf("%lld%lld", &N, &M);
}

int solve(){
	if(M < N){
		return M;
	}

	int ans = N-2;
	M -= N - 1;
	for(int cur=1;M>0;cur++){
		ans--;
		M -= cur;
	}
	return ans;
}

int main(){
	int T;
	scanf("%d", &T);
	for(;T--;){
		init();
		printf("%d\n", solve());
	}

	return 0;
}