結果

問題 No.277 根掘り葉掘り
ユーザー miyo2580miyo2580
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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.hpp
template <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) Graph
UnweightedGraph 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 Graph
template <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 Edges
template <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;
else
c = 1;
if (is_1origin) x--, y--;
es.emplace_back(x, y, c);
}
return es;
}
// Input of Adjacency Matrix
template <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;
else
c = 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 i
template <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 sum
vector<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]);
// update
dp[cur] = par == -1 ? head.back() : f1(pval, head.back());
// propagate
int 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0