結果
問題 |
No.812 Change of Class
|
ユーザー |
![]() |
提出日時 | 2020-12-08 15:03:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 536 ms / 4,000 ms |
コード長 | 961 bytes |
コンパイル時間 | 2,473 ms |
コンパイル使用メモリ | 202,744 KB |
最終ジャッジ日時 | 2025-01-16 19:43:14 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:37:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 37 | scanf("%d %d",&p,&q); | ~~~~~^~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000000 vector<int> bfs(vector<vector<int>> E,int start){ vector<int> dis(E.size(),Inf); dis[start] = 0; queue<int> Q; Q.push(start); while(Q.size()>0){ int u = Q.front(); Q.pop(); rep(i,E[u].size()){ int v = E[u][i]; if(dis[v]!=Inf)continue; dis[v] = dis[u]+1; Q.push(v); } } return dis; } int main(){ int N,M; cin>>N>>M; vector<vector<int>> E(N,vector<int>()); rep(i,M){ int p,q; scanf("%d %d",&p,&q); p--;q--; E[p].push_back(q); E[q].push_back(p); } int Q; cin>>Q; rep(i,Q){ int A; cin>>A; vector<int> ret = bfs(E,A-1); int ans = 0; int maxi = 0; rep(i,ret.size()){ if(ret[i]==Inf)continue; ans++; maxi = max(maxi,ret[i]); } ans--; cout<<ans<<' '; ans = 0; while(maxi>1){ ans++; maxi = (maxi+1)/2; } cout<<ans<<endl; } return 0; }