結果
問題 | No.812 Change of Class |
ユーザー |
![]() |
提出日時 | 2019-04-12 21:56:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 172 ms / 4,000 ms |
コード長 | 1,361 bytes |
コンパイル時間 | 2,171 ms |
コンパイル使用メモリ | 200,588 KB |
最終ジャッジ日時 | 2025-01-07 01:47:40 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
#include <bits/stdc++.h> #define rep(i, a, n) for(int i = a; i < n; i++) #define int long long using namespace std; typedef pair<int, int> P; const int mod = 1000000007; const int INF = 1e18; int n, m; vector<int> G[100010]; int d[100010]; signed main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> m; rep(i, 0, m){ int p, q; cin >> p >> q; p--; q--; G[p].push_back(q); G[q].push_back(p); } int Q; cin >> Q; while(Q--){ int a; cin >> a; a--; rep(i, 0, n) d[i] = -1; queue<int> q; q.push(a); d[a] = 0; while(!q.empty()){ int tmp = q.front(); q.pop(); for(auto i : G[tmp]){ if(d[i] != -1) continue; d[i] = d[tmp] + 1; q.push(i); } } int ans = 0, day = 0; rep(i, 0, n){ if(d[i] != -1){ ans++; day = max(day, d[i]); } } if(ans == 0) cout << 0 << ' ' << 0 << endl; else{ int now = 1; for(int j = 0;; j++){ if(day <= now){ day = j; break; } now *= 2; } cout << ans - 1 << ' ' << day << endl; } } }