結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2016-05-13 12:32:12 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 54 ms / 3,000 ms |
コード長 | 1,224 bytes |
コンパイル時間 | 545 ms |
コンパイル使用メモリ | 60,372 KB |
実行使用メモリ | 20,352 KB |
最終ジャッジ日時 | 2024-10-05 14:16:50 |
合計ジャッジ時間 | 2,161 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:41:9: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 41 | scanf("%d",&N); | ~~~~~^~~~~~~~~ main.cpp:44:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 44 | scanf("%d%d",&a,&b); | ~~~~~^~~~~~~~~~~~~~
ソースコード
#include <iostream> #include <vector> #include <cstdio> using namespace std; vector<int> edge[100001]; int dist[100001]; void update(int cur, int par, int d){ if( dist[cur] <= d ) return; dist[cur]=d; for( int ei=0; ei < (int) edge[cur].size(); ei++){ int nxt = edge[cur][ei]; if( nxt==par ) continue; update(nxt, cur, d+1); } } int rec(int cur, int par, int d){ dist[cur]=d; int tmpdist = 100001; for( int ei=0; ei < (int) edge[cur].size(); ei++){ int nxt = edge[cur][ei]; if( nxt==par ) continue; tmpdist = min(tmpdist,rec(nxt, cur, d+1)); } if(tmpdist==100001) tmpdist=0; if(tmpdist < d ){ for( int ei=0; ei < (int) edge[cur].size(); ei++){ int nxt = edge[cur][ei]; if( nxt==par ) continue; update(nxt, cur, tmpdist+1); } } dist[cur]=min(dist[cur],tmpdist); return tmpdist+1; } int main(){ int N; scanf("%d",&N); for( int i = 0 ; i < N-1; i++ ){ int a,b; scanf("%d%d",&a,&b); a--;b--; edge[a].push_back(b); edge[b].push_back(a); } for( int i=0;i<100001; i++) dist[i]=100001; rec(0,0,0); for( int i=0; i <N; i++ ) printf("%d\n",dist[i]); return 0; }