結果
問題 | No.277 根掘り葉掘り |
ユーザー |
|
提出日時 | 2018-10-31 19:19:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 163 ms / 3,000 ms |
コード長 | 1,224 bytes |
コンパイル時間 | 839 ms |
コンパイル使用メモリ | 80,508 KB |
実行使用メモリ | 11,280 KB |
最終ジャッジ日時 | 2024-11-19 12:43:24 |
合計ジャッジ時間 | 3,462 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include<iostream>#include<vector>#include<stack>using namespace std;int main(){int n;cin >> n;int INF = 100001;vector<vector<int>> v(n+1);vector<int> r(n+1, INF), l(n+1, INF);vector<int> deg(n+1, 0);int x, y;for(int i = 0; i < n-1; i++){cin >> x >> y;v[x].push_back(y);v[y].push_back(x);deg[x]++;deg[y]++;}stack<pair<int,int>> s;s.push({1, 0});while(!s.empty()){pair<int,int> p = s.top(); s.pop();r[p.first] = p.second;for(int next : v[p.first]){if(r[next] != INF) continue;s.push({next, p.second+1});}}for(int i = 2; i <= n; i++){if(deg[i] != 1) continue;s.push({i, 0});while(!s.empty()){pair<int,int> now = s.top(); s.pop();if(now.second >= l[now.first]) continue;l[now.first] = now.second;for(int next : v[now.first]){if(now.second + 1 < l[next]){s.push({next, now.second + 1});}}}}for(int i = 1; i <= n; i++) printf("%d\n", min(l[i], r[i]));return 0;}