結果
問題 | No.277 根掘り葉掘り |
ユーザー |
|
提出日時 | 2020-02-27 20:48:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 228 ms / 3,000 ms |
コード長 | 686 bytes |
コンパイル時間 | 856 ms |
コンパイル使用メモリ | 78,196 KB |
実行使用メモリ | 18,248 KB |
最終ジャッジ日時 | 2024-10-13 16:01:06 |
合計ジャッジ時間 | 4,179 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
コンパイルメッセージ
main.cpp:28:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 28 | main() | ^~~~
ソースコード
#include<iostream>#include<vector>#include<algorithm>#include<queue>using namespace std;int N;vector<int>G[1<<17];int L[1<<17],R[1<<17];queue<int>P;void dfs(int u,int p,int d){R[u]=d;bool flag=true;for(int v:G[u]){if(p!=v){dfs(v,u,d+1);flag=false;}}if(flag){L[u]=0;P.push(u);}}main(){cin>>N;for(int i=1;i<N;i++){int u,v;cin>>u>>v;u--,v--;G[u].push_back(v);G[v].push_back(u);}for(int i=0;i<N;i++)L[i]=114514;dfs(0,-1,0);while(!P.empty()){int u=P.front();P.pop();for(int v:G[u]){if(L[v]>L[u]+1){L[v]=L[u]+1;P.push(v);}}}for(int i=0;i<N;i++)cout<<min(L[i],R[i])<<endl;}