結果
問題 | No.812 Change of Class |
ユーザー |
![]() |
提出日時 | 2019-04-13 00:07:16 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 185 ms / 4,000 ms |
コード長 | 943 bytes |
コンパイル時間 | 641 ms |
コンパイル使用メモリ | 66,348 KB |
実行使用メモリ | 9,468 KB |
最終ジャッジ日時 | 2024-06-12 19:59:18 |
合計ジャッジ時間 | 6,643 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
#include <iostream> #include <vector> #include <queue> #define inf 1000000000 using namespace std; int n, m; vector<int> G[100005]; int dist[100005]; void bfs(int s) { dist[s] = 0; queue<int> Q; Q.push(s); int v; while(Q.size()){ v = Q.front(); Q.pop(); for(int i = 0; i < G[v].size(); i++){ if(dist[G[v][i]] < inf) continue; dist[G[v][i]] = dist[v] + 1; Q.push(G[v][i]); } } } int main(void) { cin >> n >> m; int u, v; for(int i = 1; i <= m; i++){ cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } int Q, a; cin >> Q; for(int q = 0; q < Q; q++){ cin >> a; for(int i = 1; i <= n; i++) dist[i] = inf; bfs(a); int cnt = 0, mx = 0; for(int i = 1; i <= n; i++) if(dist[i] < inf) cnt++; cout << cnt-1 << " "; for(int i = 1; i <= n; i++) if(dist[i] < inf) mx = max(mx, dist[i]); for(int i = 0; ; i++){ if(mx <= (1<<i)){ cout << i << endl; break; } } } return 0; }