結果
問題 | 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 1000000000using 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;}