結果

問題 No.2677 Minmax Independent Set
ユーザー ltf0501
提出日時 2025-03-20 18:00:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 202 ms / 2,000 ms
コード長 2,431 bytes
コンパイル時間 2,360 ms
コンパイル使用メモリ 204,056 KB
実行使用メモリ 89,084 KB
最終ジャッジ日時 2025-03-20 18:00:59
合計ジャッジ時間 11,539 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 61
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In lambda function:
main.cpp:60:33: warning: range-based ‘for’ loops with initializer only available with ‘-std=c++20’ or ‘-std=gnu++20’ [-Wc++20-extensions]
   60 |                 for (int i = 0; auto &v : g[u]) {
      |                                 ^~~~
main.cpp:72:33: warning: range-based ‘for’ loops with initializer only available with ‘-std=c++20’ or ‘-std=gnu++20’ [-Wc++20-extensions]
   72 |                 for (int i = 0; auto &v : g[u]) {
      |                                 ^~~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
template<typename Ostream, typename ...Ts>
Ostream& operator << (Ostream &os, const pair<Ts...> &p){
  return os << "{" << p.first << ", " << p.second << "}";
}
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream, ostream>::value, Ostream&>::type operator<<(Ostream& os,  const Cont& v){
  os << "[ ";
	for(auto &x : v)
    os << x << ' ';
	return os << "]";
}
void dbg_cerr() { cerr << "\e[0m\n"; }
template<typename Head, typename... Tail> void dbg_cerr(Head H, Tail... T) { cerr << ' ' << H; dbg_cerr(T...); }
#ifdef LTF
#define DEBUG(...) cerr << "\e[1;31m[" #__VA_ARGS__ "]:", dbg_cerr(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

constexpr int64_t kInf = int64_t(1e18);

void Solve() {
	int N; cin >> N;
	vector g(N, vector<int>());
	for (int i = 0; i < N - 1; i++) {
		int x, y; cin >> x >> y;
		x--, y--;
		g[x].push_back(y), g[y].push_back(x);
	}

	auto merge = [&](auto a, auto b) {
		auto c = a;
		c[0] = a[0] + b[0], c[1] = a[1] + b[1];
		return c;
	};
	auto apply = [&](auto a) {
		auto b = a;
		b[1] = a[0], b[0] = max(a[0], a[1] + 1);
		return b;
	};
	// 0: not contain, 1: contain
	vector<array<int, 2>> dp(N, {0, 0});
	auto Dfs1 = [&](auto self, int u, int fa) -> void {
		for (int v : g[u]) {
			if (v == fa) continue;

			self(self, v, u);
			dp[u] = merge(dp[u], apply(dp[v]));
		}
	};
	Dfs1(Dfs1, 0, -1);

	vector<array<int, 2>> dp2(N, {0, 0});
	auto Dfs2 = [&](auto self, auto &top_dp, int u, int fa) -> void {
		int sz = int(g[u].size());
		vector<array<int, 2>> ds(sz);

		for (int i = 0; auto &v : g[u]) {
			if (v == fa) ds[i] = top_dp;
			else ds[i] = apply(dp[v]);
			i++;
		}

		vector<array<int, 2>> dp_l(sz + 1, {0, 0});
		vector<array<int, 2>> dp_r(sz + 1, {0, 0});
		for (int i = 0; i + 1 <= sz; i++) dp_l[i + 1] = merge(dp_l[i], ds[i]);
		for (int i = sz - 1; i >= 0; i--) dp_r[i] = merge(dp_r[i + 1], ds[i]);
		
		dp2[u] = dp_l.back();
		for (int i = 0; auto &v : g[u]) {
			// [0, i) & [i + 1, sz)
			if (v != fa) {
				auto down_dp = apply(merge(dp_l[i], dp_r[i + 1]));
				self(self, down_dp, v, u);
			}
			i++;
		}
	};
	array<int, 2> basis = {0, 0};
	Dfs2(Dfs2, basis, 0, -1);

	int ans = N;
	for (int i = 0; i < N; i++) ans = min(ans, dp2[i][1]);
	cout << ans + 1 << '\n';
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
  int T = 1;
  // cin >> T;
  while (T--) {
    Solve();
  }
  return 0;
}
0