結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2020-02-03 01:37:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 215 ms / 3,000 ms |
コード長 | 1,767 bytes |
コンパイル時間 | 2,075 ms |
コンパイル使用メモリ | 202,712 KB |
最終ジャッジ日時 | 2025-01-08 21:57:46 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using PII = std::pair<int, int>;using PLL = std::pair<ll, ll>;#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)vector<int> depth, height, parent;vector<vector<int>> nodes;void dfs1(int s, int d){depth[s] = d;for (auto z : nodes[s])if (z != parent[s]){parent[z] = s;dfs1(z, d+1);}}void bfs(vector<int> leaf, int n){int turn = 0;vector<int> search, new_search;search = leaf;while (!search.empty()){for (auto i : search){height[i] = min(height[i], turn);for (auto j : nodes[i]){if (height[j] == n){new_search.push_back(j);height[j] = turn + 1;}}}search.clear();search = new_search;new_search.clear();turn++;}}int main(){#ifdef DEBUGcout << "DEBUG MODE" << endl;ifstream in("input.txt"); //for debugcin.rdbuf(in.rdbuf()); //for debug#endifint n, a, b;cin >> n;vector<int> leaf;depth.resize(n), height.resize(n), parent.resize(n), nodes.resize(n);parent[0] = -1;rep(i, n-1){cin >> a >> b;a--, b--;nodes[a].push_back(b);nodes[b].push_back(a);}dfs1(0, 0);fill(height.begin(), height.end(), n);rep(i, n)if (nodes[i].size() == 1)leaf.push_back(i);bfs(leaf, n);// rep(i, n)// cout << height[i] << endl;rep(i, n)cout << min(depth[i], height[i]) << endl;return 0;}