結果
問題 | No.812 Change of Class |
ユーザー |
![]() |
提出日時 | 2019-04-12 23:11:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 196 ms / 4,000 ms |
コード長 | 1,010 bytes |
コンパイル時間 | 1,631 ms |
コンパイル使用メモリ | 174,804 KB |
実行使用メモリ | 10,640 KB |
最終ジャッジ日時 | 2024-06-12 19:52:10 |
合計ジャッジ時間 | 7,989 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
#include<bits/stdc++.h> #define REP(i,n) for(int i=0;i<(n);i++) #define ALL(v) (v).begin(),(v).end() #define SZ(x) ((int)(x).size()) #define int long long using namespace std; typedef vector<int> vint; typedef pair<int,int> pint; const int size=100010; const int INF=1e9; vint G[size]; int N,M; int calc(int dist) { if(dist==1) return 0; return calc((dist+1)/2)+1; } void bfs(int s) { vint dist(N); REP(i,N) dist[i]=INF; dist[s]=0; queue<int> Q; Q.push(s); while(!Q.empty()){ int v=Q.front(); Q.pop(); for(int u:G[v]){ if(dist[u]!=INF) continue; dist[u]=dist[v]+1; Q.push(u); } } int cnt=0,day=0; REP(i,N){ if(dist[i]!=INF and dist[i]>0){ cnt++; int d=calc(dist[i]); day=max(day,d); } } cout<<cnt<<' '<<day<<endl; } signed main() { cin>>N>>M; REP(i,M){ int a,b; cin>>a>>b; a--; b--; G[a].push_back(b); G[b].push_back(a); } int Q; cin>>Q; while(Q--){ int q; cin>>q; q--; bfs(q); } }