結果
問題 |
No.812 Change of Class
|
ユーザー |
|
提出日時 | 2019-04-14 03:55:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 140 ms / 4,000 ms |
コード長 | 1,241 bytes |
コンパイル時間 | 2,027 ms |
コンパイル使用メモリ | 173,968 KB |
実行使用メモリ | 9,852 KB |
最終ジャッジ日時 | 2024-06-12 20:50:52 |
合計ジャッジ時間 | 6,352 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
#include <bits/stdc++.h> using namespace std; pair<int, int> solve(int s, int N, const vector<vector<int>> & edges){ vector<int> dist(N, -1); int f = 0; int d = 0; dist[s] = d; vector<int> pool = {s}; vector<int> next_pool; while (pool.size()){ next_pool.clear(); ++d; for (auto p: pool){ for (auto q: edges[p]){ if (dist[q] == -1){ dist[q] = d; next_pool.push_back(q); ++f; } } } swap(pool, next_pool); } d = *max_element(dist.begin(), dist.end()); int days = 0; int tmp = 1; while (d > tmp){ ++days; tmp *= 2; } return make_pair(f, days); } int main() { ios::sync_with_stdio(false); cout.tie(0); int N, M; cin >> N >> M; vector<vector<int>> edges(N); while (M--){ int p, q; cin >> p >> q; edges[p - 1].push_back(q - 1); edges[q - 1].push_back(p - 1); } int Q; cin >> Q; while (Q--){ int A; cin >> A; auto ans = solve(A - 1, N, edges); cout << ans.first << ' ' << ans.second << "\n"; } return 0; }