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