結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2018-04-02 22:58:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 276 ms / 3,000 ms |
コード長 | 2,817 bytes |
コンパイル時間 | 1,413 ms |
コンパイル使用メモリ | 128,036 KB |
実行使用メモリ | 32,328 KB |
最終ジャッジ日時 | 2024-06-26 06:51:37 |
合計ジャッジ時間 | 5,443 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
# include <iostream># include <algorithm>#include <array># include <cassert>#include <cctype>#include <climits>#include <numeric># include <vector># include <string># include <set># include <map># include <cmath># include <iomanip># include <functional># include <tuple># include <utility># include <stack># include <queue># include <list># include <bitset># include <complex># include <chrono># include <random># include <limits.h># include <unordered_map># include <unordered_set># include <deque># include <cstdio># include <cstring>#include <stdio.h>#include <stdlib.h>#include <cstdint>using namespace std;using LL = long long;using ULL = unsigned long long;constexpr long long MOD = 1000000000 + 7;constexpr long long INF = std::numeric_limits<long long>::max();const double PI = acos(-1);#define fir first#define sec second#define debug(x) cerr<<#x<<": "<<x<<'\n'typedef pair<LL, LL> Pll;typedef pair<LL, pair<LL, LL>> Ppll;typedef pair<LL, pair<LL, bitset<100001>>> Pbll;typedef pair<LL, pair<LL, vector<LL>>> Pvll;typedef pair<LL, LL> Vec2;struct Tll { LL first, second, third; };typedef pair<LL, Tll> Ptll;#define rep(i,rept) for(LL i=0;i<rept;i++)#define Mfor(i,mf) for(LL i=mf-1;i>=0;i--)LL h, w, n, m, k, s, t, q, sum, last, cnt, ans[100010],a[1000],d[100010];string str;struct Edge { LL to, cost; };vector<Edge>vec[100010];bool f;char c;void YN(bool f) {if (f)cout << "YES" << endl;elsecout << "NO" << endl;}void yn(bool f) {if (f)cout << "Yes" << endl;elsecout << "No" << endl;}void dfs1(LL idx, LL par){bool ff = 0;if (par != -1)d[idx] = min(d[idx], d[par] + 1);for (Edge &e : vec[idx]) {if (e.to == par) continue;ff = 1;dfs1(e.to, idx);d[idx] = min(d[idx], d[e.to] + e.cost);}if (ff == 0)d[idx] = 0;}LL dfs2(LL idx, LL d_par, LL par){vector<pair<LL, LL>> d_child;d_child.emplace_back(INF/2, -1);for (Edge &e : vec[idx]) {if (e.to == par) d_child.emplace_back(d_par + e.cost, e.to);else d_child.emplace_back(e.cost + d[e.to], e.to);}sort(d_child.rbegin(), d_child.rend(), [](Pll x, Pll y) {return x.fir > y.fir; });LL ret = min(d[idx],d_child[0].first);for (Edge &e : vec[idx]) {if (e.to == par) continue;// 基本は d_child() の最大が d_par になるが, e.to の部分木が最大値のときはそれを取り除く必要があるret = min(ret, dfs2(e.to, d_child[d_child[0].second == e.to].first, idx)+1);}ans[idx] = min(ans[idx], ret);return (ret);}int main() {cin >> n;rep(i, n)d[i] = INF / 4;rep(i, n)ans[i] = INF / 4;rep(i, n - 1) {LL x, y;cin >> x >> y;x--, y--;vec[x].push_back(Edge{ y,1 });vec[y].push_back(Edge{ x,1 });}d[0] = 0;dfs1(0, -1);dfs2(0, 0, -1);rep(i, n)cout << ans[i] << endl;return 0;}