結果
問題 | No.812 Change of Class |
ユーザー |
|
提出日時 | 2019-04-12 21:43:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 126 ms / 4,000 ms |
コード長 | 1,411 bytes |
コンパイル時間 | 1,524 ms |
コンパイル使用メモリ | 175,288 KB |
実行使用メモリ | 9,300 KB |
最終ジャッジ日時 | 2024-06-12 06:41:34 |
合計ジャッジ時間 | 5,924 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;const int INF = 1e9;vector<int> bfs(int src, int n, vector< vector<int> >& g) {vector<int> res(n, INF);res[src] = 0;queue<int> q;q.push(src);while (!q.empty()) {int cur = q.front();q.pop();for (int nex : g[cur]) {if (res[nex] != INF) continue;res[nex] = res[cur] + 1;q.push(nex);}}return res;}int main() {cin.tie(0);ios::sync_with_stdio(false);int n, m;cin >> n >> m;vector< vector<int> > g(n);for (int i = 0; i < m; i++) {int p, q;cin >> p >> q;p--; q--;g[p].push_back(q);g[q].push_back(p);}int q;cin >> q;for (int i = 0; i < q; i++) {int a;cin >> a;a--;vector<int> d = bfs(a, n, g);int cnt = 0;int maxd = 0;for (int j = 0; j < n; j++) {if (d[j] == INF) continue;cnt++;maxd = max(maxd, d[j]);}cnt = max(cnt - 1, 0);int ans = 0;if (maxd > 0) {for (int j = 0; j <= 17; j++) {if (maxd <= (1 << j)) {ans = j;break;}}}cout << cnt << " " << ans << "\n";}return 0;}