結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2020-05-28 02:14:50 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 251 ms / 3,000 ms |
コード長 | 2,670 bytes |
コンパイル時間 | 1,397 ms |
コンパイル使用メモリ | 165,212 KB |
実行使用メモリ | 23,808 KB |
最終ジャッジ日時 | 2024-10-13 04:00:20 |
合計ジャッジ時間 | 4,991 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
/*** @FileName a.cpp* @Author kanpurin* @Created 2020.05.28 02:14:42**/#include "bits/stdc++.h"using namespace std;typedef long long ll;// [問題設定]// それぞれ1からNまでの番号が付いたN個の頂点が、N-1本の無向辺によって繋がれたグラフが与えられる。// 各頂点について、その頂点からスタートしてすべての頂点を訪れるための最短のステップ数を出力せよ。//// [解法]// 各頂点からの最遠頂点までの距離を辺の数の2倍から引く// 全方位木DPで解くusing T = int; // データ型int n; // 頂点vector< vector< int > > tree;vector< T > dist; // 根付き木中の i のvector< T > ans;vector< int > dist1;void dfs1(int v, int p = -1) {T res = 1000000;for (auto& u : tree[v]) {if (u == p) continue;dfs1(u, v);res = min(res, dist[u] + 1);}if (res == 1000000) {dist[v] = 0;} else {dist[v] = res;}}void dfs2(int v, T d_par, int p = -1) {// v における答えの計算ans[v] = min(d_par + 1, dist[v]);// 左右からの累積演算を用いて子に送る d_par の計算// lf[i] : [:i-1]の演算結果// ri[i] : [i+1:]の演算結果auto f = [](T a, T b) { return min(a, b); }; // 演算int e = 1000000; // 演算の単位元vector< T > lf(tree[v].size(), e), ri(tree[v].size(), e); // 累積配列for (int i = 1; i < tree[v].size(); i++) {if (tree[v][i - 1] == p)lf[i] = f(d_par, lf[i - 1]);elself[i] = f(dist[tree[v][i - 1]], lf[i - 1]);}for (int i = tree[v].size() - 2; i >= 0; i--) {if (tree[v][i + 1] == p)ri[i] = f(d_par, ri[i + 1]);elseri[i] = f(dist[tree[v][i + 1]], ri[i + 1]);}for (int i = 0; i < tree[v].size(); i++) {if (tree[v][i] == p) continue;dfs2(tree[v][i], f(lf[i], ri[i]) + 1, v);}}// 根からの距離void dfs(int v, int d = 0, int p = -1) {dist1[v] = d;for (int u : tree[v]) {if (p == u) continue;dfs(u, d + 1, v);}}int main() {cin >> n;tree.resize(n);dist1.resize(n);dist.resize(n);ans.resize(n);for (int i = 0; i < n - 1; i++) {int u, v;cin >> u >> v;u--;v--;tree[u].push_back(v);tree[v].push_back(u);}dfs1(0);dfs2(0, 1000000);dfs(0);for (int i = 0; i < n; i++) {cout << min(dist1[i], ans[i]) << endl;}return 0;}