結果
問題 | 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 longusing 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);}}