結果
問題 | No.277 根掘り葉掘り |
ユーザー |
|
提出日時 | 2023-12-04 21:21:41 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 136 ms / 3,000 ms |
コード長 | 5,132 bytes |
コンパイル時間 | 2,950 ms |
コンパイル使用メモリ | 178,772 KB |
実行使用メモリ | 43,136 KB |
最終ジャッジ日時 | 2024-09-26 23:14:06 |
合計ジャッジ時間 | 4,229 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define repd(i,a,b) for (ll i=(a);i<(b);i++)#define rep(i,n) repd(i,0,n)#define all(x) (x).begin(),(x).end()template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }typedef long long ll;typedef pair<ll,ll> P;typedef vector<ll> vec;using Graph = vector<vector<ll>>;const long long INF = 1LL<<60;const long long MOD = 1000000007;//https://nyaannyaan.github.io/library/graph/graph-template.hpptemplate <typename T>struct edge {int src, to;T cost;edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}edge &operator=(const int &x) {to = x;return *this;}operator int() const { return to; }};template <typename T>using Edges = vector<edge<T>>;template <typename T>using WeightedGraph = vector<Edges<T>>;using UnweightedGraph = vector<vector<int>>;// Input of (Unweighted) GraphUnweightedGraph graph(int N, int M = -1, bool is_directed = false,bool is_1origin = true) {UnweightedGraph g(N);if (M == -1) M = N - 1;for (int _ = 0; _ < M; _++) {int x, y;cin >> x >> y;if (is_1origin) x--, y--;g[x].push_back(y);if (!is_directed) g[y].push_back(x);}return g;}// Input of Weighted Graphtemplate <typename T>WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false,bool is_1origin = true) {WeightedGraph<T> g(N);if (M == -1) M = N - 1;for (int _ = 0; _ < M; _++) {int x, y;cin >> x >> y;T c;cin >> c;if (is_1origin) x--, y--;g[x].emplace_back(x, y, c);if (!is_directed) g[y].emplace_back(y, x, c);}return g;}// Input of Edgestemplate <typename T>Edges<T> esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) {Edges<T> es;for (int _ = 0; _ < M; _++) {int x, y;cin >> x >> y;T c;if (is_weighted)cin >> c;elsec = 1;if (is_1origin) x--, y--;es.emplace_back(x, y, c);}return es;}// Input of Adjacency Matrixtemplate <typename T>vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true,bool is_directed = false, bool is_1origin = true) {vector<vector<T>> d(N, vector<T>(N, INF));for (int _ = 0; _ < M; _++) {int x, y;cin >> x >> y;T c;if (is_weighted)cin >> c;elsec = 1;if (is_1origin) x--, y--;d[x][y] = c;if (!is_directed) d[y][x] = c;}return d;}/*** @brief グラフテンプレート* @docs docs/graph/graph-template.md*///https://nyaannyaan.github.io/library/tree/rerooting.hpp// Rerooting// f1(c1, c2) ... merge value of child node// f2(memo[i], chd, par) ... return value from child node to parent node// memo[i] ... result of subtree rooted i// dp[i] ... result of tree rooted itemplate <typename T, typename G, typename F1, typename F2>struct Rerooting {const G &g;const F1 f1;const F2 f2;vector<T> memo, dp;T I;Rerooting(const G &_g, const F1 _f1, const F2 _f2, const T &I_): g(_g), f1(_f1), f2(_f2), memo(g.size(), I_), dp(g.size(), I_), I(I_) {dfs(0, -1);efs(0, -1, I);}const T &operator[](int i) const { return dp[i]; }void dfs(int cur, int par) {for (auto &dst : g[cur]) {if (dst == par) continue;dfs(dst, cur);memo[cur] = f1(memo[cur], f2(memo[dst], dst, cur));}}void efs(int cur, int par, const T &pval) {// get cumulative sumvector<T> buf;for (auto dst : g[cur]) {if (dst == par) continue;buf.push_back(f2(memo[dst], dst, cur));}vector<T> head(buf.size() + 1), tail(buf.size() + 1);head[0] = tail[buf.size()] = I;for (int i = 0; i < (int)buf.size(); i++) head[i + 1] = f1(head[i], buf[i]);for (int i = (int)buf.size() - 1; i >= 0; i--)tail[i] = f1(tail[i + 1], buf[i]);// updatedp[cur] = par == -1 ? head.back() : f1(pval, head.back());// propagateint idx = 0;for (auto &dst : g[cur]) {if (dst == par) continue;efs(dst, cur, f2(f1(pval, f1(head[idx], tail[idx + 1])), cur, dst));idx++;}}};/*** @brief Rerooting(全方位木DP)* @docs docs/tree/rerooting.md*/int main(){ios::sync_with_stdio(false);cin.tie(0);ll n;cin>>n;auto g=graph(n,n-1,0,1);auto f1=[&](ll x,ll y){return min(x,y);};auto f2=[&](ll x,ll chd,ll p){if(g[chd].size()==1)x=0;if(g[p].size()==1)x=-1;return x+1;};Rerooting<ll,decltype(g),decltype(f1),decltype(f2)> dp(g,f1,f2,INF);vec ans(n);function<void(ll,ll,ll)> dfs=[&](ll x,ll p,ll d){for(ll nx:g[x]){if(nx==p)continue;dfs(nx,x,d+1);}ans[x]=d;};dfs(0,-1,0);ll id=0;for(ll i:dp.dp){chmin(ans[id],i);id++;}rep(i,n)cout<<ans[i]<<'\n';return 0;}