結果
問題 | No.277 根掘り葉掘り |
ユーザー |
|
提出日時 | 2021-02-15 05:09:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 100 ms / 3,000 ms |
コード長 | 2,514 bytes |
コンパイル時間 | 1,382 ms |
コンパイル使用メモリ | 137,192 KB |
最終ジャッジ日時 | 2025-01-18 21:08:27 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <cmath>#include <queue>#include <string>#include <map>#include <set>#include <stack>#include <tuple>#include <deque>#include <array>#include <numeric>#include <bitset>#include <iomanip>#include <cassert>#include <chrono>#include <random>#include <limits>#include <iterator>#include <functional>#include <sstream>#include <fstream>#include <complex>#include <cstring>#include <unordered_map>#include <unordered_set>using namespace std;using ll = long long;constexpr int INF = 1001001001;// constexpr int mod = 1000000007;constexpr int mod = 998244353;template<class T>inline bool chmax(T& x, T y){if(x < y){x = y;return true;}return false;}template<class T>inline bool chmin(T& x, T y){if(x > y){x = y;return true;}return false;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<vector<int>> g(n);for(int i = 1; i < n; ++i){int u, v;cin >> u >> v;--u, --v;g[u].emplace_back(v);g[v].emplace_back(u);}vector<int> dep(n), dp(n, INF);auto dfs = [&](auto&& self, int from = 0, int d = 0, int par = -1) -> int {dep[from] = d;for(int to : g[from]){if(to != par) chmin(dp[from], self(self, to, d + 1, from) + 1);}if(dp[from] == INF) dp[from] = 0;return dp[from];};dfs(dfs);auto dp2 = dp;auto rerooting = [&](auto&& self, int from = 0, int par = -1) -> void {int V = g[from].size();vector<int> prefix(V + 1, INF), suffix(V + 1, INF);for(int i = 0; i < V; ++i){int to = g[from][i];if(to == par) prefix[i + 1] = prefix[i];else prefix[i + 1] = min(prefix[i], dp[to]);}for(int i = V - 1; i >= 0; --i){int to = g[from][i];if(to == par) suffix[i] = suffix[i + 1];else suffix[i] = min(suffix[i + 1], dp[to]);}for(int i = 0; i < V; ++i){int to = g[from][i];if(to == par) continue;chmin(dp2[to], min(prefix[i], suffix[i + 1]) + 2);if(par != -1) chmin(dp2[to], dp2[from] + 1);self(self, to, from);}};rerooting(rerooting);for(int i = 0; i < n; ++i){cout << min(dep[i], dp2[i]) << '\n';}return 0;}