Change of Class [yukicoder No.812]

https://yukicoder.me/problems/no/812

前提知識

• ダイクストラ

解説

https://yukicoder.me/submissions/338267

1日経過するたびに、距離が2の人と友達になる。
次の日もまた、距離が2の人と友達になる。
これで友達になっている人を考えると

• もともと距離1→もともと友達
• もともと距離2→1日経過で友達になった
• もともと距離3→2日経過で友達になった（1日経過で友達になった人ともともと友達）
• もともと距離4→2日経過で友達になった（1日経過で友達になった人が1日経過で友達になった人）

となる。更に1日経つと、新しく友達になる人は、その人から距離1～4の人と既に友達なので、
距離1～4+距離1～4を網羅できるので、距離1～8の人と友達になれる。
よって、距離がdだとすると、log2(d)の切り上げが最短で友達になる日時となる。
　
N人の友達関係を無向グラフとして考える。
各クエリについて、始点から連結な頂点が友達になれる頂点で、その中で最も遠い頂点が最も時間がかかる友達となる。
どちらも、ダイクストラで判別できるので、やろう。
あとは、連結を数えて、最長距離のlog2切り上げを求めると答え。

int N, M;
vector<pair<int,int>> E[101010];
int Q;
//---------------------------------------------------------------------------------------------------
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int vis[101010];
void dijk(int s, vector<ll>& D) {
	rep(i, 0, N) D[i] = infl;
	rep(i, 0, N) vis[i] = 0;

	min_priority_queue<pair<ll, int>> que;

	D[s] = 0;
	que.push({ 0, s });

	while (!que.empty()) {
		auto q = que.top(); que.pop();

		ll cst = q.first;
		int cu = q.second;

		if (vis[cu]) continue;
		vis[cu] = 1;

		fore(p, E[cu]) {
			ll cst2 = cst + p.second;
			int to = p.first;

			if (chmin(D[to], cst2)) que.push({ D[to], to });
		}
	}
}
//---------------------------------------------------------------------------------------------------
ll log2_roundup(ll x) {
	int res = 0;
	ll y = 1;
	while (y < x) {
		y *= 2;
		res++;
	}
	return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M;
	rep(i, 0, M) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		E[a].push_back({ b,1 });
		E[b].push_back({ a,1 });
	}

	cin >> Q;
	vector<ll> d(N);
	rep(q, 0, Q) {
		int s; cin >> s; s--;

		dijk(s, d);

		int ans1 = 0;
		ll ans2 = 0;
		rep(i, 0, N) if (0 < d[i] and d[i] < infl) {
			ans1++;
			chmax(ans2, log2_roundup(d[i]));
		}

		printf("%d %lld\n", ans1, ans2);
	}
}