結果
問題 | No.277 根掘り葉掘り |
ユーザー |
|
提出日時 | 2021-07-18 23:45:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 84 ms / 3,000 ms |
コード長 | 1,304 bytes |
コンパイル時間 | 1,932 ms |
コンパイル使用メモリ | 201,076 KB |
最終ジャッジ日時 | 2025-01-23 03:15:38 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> using namespace std; int R[100005]; int L[100005]; vector <int> adj[100005]; int n, x, y; void dfs(int now,int prev) { for (auto next : adj[now]) { if (prev == next) continue; R[next] = R[now] + 1; dfs(next, now); } } int solve(int now, int prev) { if (L[now] != -1) { return L[now]; } int res = 1e9; for (auto next : adj[now]) { if (prev == next) { continue; } res = min(res, solve(next, now) + 1); } if (res >= 1e9) { res = 0; } L[now] = res; return L[now]; } void dfs2(int now, int prev, int U) { multiset <int> S; L[now] = min(L[now], U); for (auto next : adj[now]) { if (next == prev) continue; S.insert(L[next] + 1); } for (auto next : adj[now]) { if (prev == next) continue; S.erase(L[next] + 1); if (!S.empty()) { int MIN = *S.begin(); MIN = min(MIN, U); dfs2(next, now, MIN + 1); } else { dfs2(next, now, U + 1); } S.insert(L[next] + 1); } } int main(void) { cin.tie(0); ios::sync_with_stdio(false); cin >> n; for (int i = 0; i < n - 1; i++) { cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); } memset(L, -1, sizeof(L)); R[1] = 0; dfs(1, 0); solve(1, 0); dfs2(1, 0, 1e9); for (int i = 1; i <= n; i++) { cout << min(L[i], R[i]) << '\n'; } return 0; }