結果

問題 No.2677 Minmax Independent Set
ユーザー t98slidert98slider
提出日時 2024-03-15 23:03:24
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 240 ms / 2,000 ms
コード長 3,193 bytes
コンパイル時間 2,105 ms
コンパイル使用メモリ 213,236 KB
実行使用メモリ 73,520 KB
最終ジャッジ日時 2024-09-30 02:38:05
合計ジャッジ時間 9,687 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 61
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
template<class T> istream& operator >> (istream& is, vector<T>& vec) {
for(T& x : vec) is >> x;
return is;
}
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) {
if(vec.empty()) return os;
os << vec[0];
for(auto it = vec.begin(); ++it != vec.end(); ) os << ' ' << *it;
return os;
}
struct ReRooting{
using T = array<int, 2>;
const T identity = T({0, 0}); //merge
int n;
vector<vector<int>> G;
vector<vector<T>> dp;
vector<T> ans;
//viR
T receive(int v, int i, T &R){
return T(R);
}
//lreceivemerge
//merge
T merge(T l, T r){
return T({l[0] + r[0], l[1] + r[1]});
}
//
T givep(int v, T cum){
return T({max(cum[0], 1 + cum[1]), cum[0]});
}
ReRooting() {}
ReRooting(int N):n(N){
G.resize(N);
dp.resize(N);
ans.resize(N, identity);
}
void add_edge(int a, int b) {
G[a].emplace_back(b);
G[b].emplace_back(a);
}
void read(){
int a, b;
for(int i = 1; i < n; i++){
cin >> a >> b;
a--, b--;
G[a].emplace_back(b);
G[b].emplace_back(a);
}
}
void build() {
dfs(0); // DP
dfs2(0, identity); // DP
}
T dfs(int v, int p = -1) {
T res = identity;
int deg = G[v].size();
dp[v] = vector<T>(deg, identity);
for (int i = 0; i < deg; i++) {
int u = G[v][i];
if (u == p) continue;
dp[v][i] = dfs(u, v);
res = merge(res, receive(v, i, dp[v][i]) );
}
return givep(v,res);
}
void dfs2(int v, const T& dp_p, int p = -1) {
int deg = G[v].size();
for (int i = 0; i < deg; i++) { // dfsDP
if (G[v][i] == p){dp[v][i] = dp_p; break;}
}
vector<T> dp_l(deg + 1, identity), dp_r(deg + 1, identity); // merge
for (int i = 0; i < deg; i++) {
dp_l[i + 1] = merge(dp_l[i], receive(v, i, dp[v][i]));
}
for (int i = deg - 1; i >= 0; i--) {
dp_r[i] = merge(dp_r[i + 1], receive(v, i, dp[v][i]));
}
//ans[v] = dp_l[deg]; // v
for(int i = 0; i < deg; i++){
ans[v][1] += dp[v][i][1];
}
ans[v][1]++;
for (int i = 0; i < deg; i++) { //
int u = G[v][i];
if (u == p) continue;
dfs2(u, givep(v,merge(dp_l[i], dp_r[i + 1])),v);
}
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
ReRooting g(n);
g.read();
g.build();
int ans = 1 << 30;
for(int v = 0; v < n; v++) ans = min(ans, g.ans[v][1]);
cout << ans << '\n';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0