結果
問題 | No.277 根掘り葉掘り |
ユーザー |
|
提出日時 | 2020-05-01 18:08:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 255 ms / 3,000 ms |
コード長 | 978 bytes |
コンパイル時間 | 2,055 ms |
コンパイル使用メモリ | 171,532 KB |
実行使用メモリ | 17,152 KB |
最終ジャッジ日時 | 2024-12-24 12:46:05 |
合計ジャッジ時間 | 5,694 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<(int)(n);i++)using namespace std;using ll = long long ;using P = pair<int,int> ;using pll = pair<ll,ll>;constexpr int INF = 1e9;constexpr ll LINF = 1e18;constexpr int MOD = 1000000007;int n = 100005;vector<vector<int>> tree(n,vector<int>());vector<int> R(n,0);vector<int> L(n,0);int dfs(int i,int p=-1,int d=0){R[i] = d;int res = INF;for(int c:tree[i]){if(c == p) continue;res = min(res,dfs(c,i,d+1)+1);}L[i] = (res==INF ? 0 : res);return L[i];}void dfs2(int i,int p=-1){if(p != -1) L[i] = min(L[i],L[p]+1);for(int c:tree[i]){if(c==p) continue;dfs2(c,i);}}int main(){cin >> n;rep(i,n-1){int a,b;cin >> a >> b;--a;--b;tree[a].push_back(b);tree[b].push_back(a);}dfs(0);dfs2(0);rep(i,n){cout << min(L[i],R[i]) << endl;}return 0;}