#961400 (C++23) No.2677 Minmax Independent Set

提出ソース

結果

問題	No.2677 Minmax Independent Set
ユーザー	kwm_t
提出日時	2024-03-17 00:22:29
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	171 ms / 2,000 ms
コード長	2,417 bytes
コンパイル時間	3,512 ms
コンパイル使用メモリ	257,780 KB
実行使用メモリ	28,868 KB
最終ジャッジ日時	2024-03-17 00:22:41
合計ジャッジ時間	11,061 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	2 ms 6,676 KB
testcase_02	AC	2 ms 6,676 KB
testcase_03	AC	2 ms 6,676 KB
testcase_04	AC	2 ms 6,676 KB
testcase_05	AC	138 ms 19,908 KB
testcase_06	AC	140 ms 20,036 KB
testcase_07	AC	137 ms 20,036 KB
testcase_08	AC	136 ms 20,292 KB
testcase_09	AC	137 ms 20,804 KB
testcase_10	AC	110 ms 19,616 KB
testcase_11	AC	105 ms 19,620 KB
testcase_12	AC	167 ms 28,868 KB
testcase_13	AC	164 ms 22,688 KB
testcase_14	AC	141 ms 22,784 KB
testcase_15	AC	167 ms 24,756 KB
testcase_16	AC	169 ms 19,140 KB
testcase_17	AC	171 ms 19,140 KB
testcase_18	AC	94 ms 13,312 KB
testcase_19	AC	125 ms 15,172 KB
testcase_20	AC	30 ms 7,424 KB
testcase_21	AC	135 ms 16,452 KB
testcase_22	AC	8 ms 6,676 KB
testcase_23	AC	2 ms 6,676 KB
testcase_24	AC	2 ms 6,676 KB
testcase_25	AC	2 ms 6,676 KB
testcase_26	AC	2 ms 6,676 KB
testcase_27	AC	2 ms 6,676 KB
testcase_28	AC	99 ms 19,680 KB
testcase_29	AC	154 ms 25,152 KB
testcase_30	AC	2 ms 6,676 KB
testcase_31	AC	2 ms 6,676 KB
testcase_32	AC	2 ms 6,676 KB
testcase_33	AC	2 ms 6,676 KB
testcase_34	AC	2 ms 6,676 KB
testcase_35	AC	2 ms 6,676 KB
testcase_36	AC	2 ms 6,676 KB
testcase_37	AC	2 ms 6,676 KB
testcase_38	AC	2 ms 6,676 KB
testcase_39	AC	2 ms 6,676 KB
testcase_40	AC	3 ms 6,676 KB
testcase_41	AC	5 ms 6,676 KB
testcase_42	AC	7 ms 6,676 KB
testcase_43	AC	13 ms 6,676 KB
testcase_44	AC	29 ms 7,168 KB
testcase_45	AC	69 ms 11,008 KB
testcase_46	AC	157 ms 18,680 KB
testcase_47	AC	170 ms 19,012 KB
testcase_48	AC	166 ms 19,012 KB
testcase_49	AC	167 ms 19,012 KB
testcase_50	AC	34 ms 9,424 KB
testcase_51	AC	4 ms 6,676 KB
testcase_52	AC	85 ms 16,816 KB
testcase_53	AC	76 ms 15,720 KB
testcase_54	AC	3 ms 6,676 KB
testcase_55	AC	115 ms 19,736 KB
testcase_56	AC	112 ms 19,728 KB
testcase_57	AC	124 ms 19,704 KB
testcase_58	AC	118 ms 19,616 KB
testcase_59	AC	112 ms 19,612 KB
testcase_60	AC	68 ms 19,012 KB
testcase_61	AC	72 ms 19,140 KB
testcase_62	AC	71 ms 20,804 KB
testcase_63	AC	72 ms 24,388 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
//using mint = modint998244353;
//const int mod = 998244353;
//using mint = modint1000000007;
//const int mod = 1000000007;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n-1); i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
#include<vector>
#include<iostream> 
struct ReRooting {
	struct Edge {
		int to;
		Edge(int _to) :to(_to) {}
	};
	struct Data {
		int val0 = 0;
		int val1 = 0;
		int max = 0;
		Data(int val0 = 0, int val1 = 0, int max = 0) :val0(val0), val1(val1), max(max) {}
	};
	std::vector<std::vector<Edge>>g;
	std::vector<Data>dp;
	std::vector<Data>ans;
	int sz;
	ReRooting(int _sz) :sz(_sz) {
		g.resize(sz);
		dp.reserve(sz);
		ans.resize(sz);
	}
	void ReadGraph() {
		for (int i = 0; i < sz - 1; ++i) {
			int a, b; std::cin >> a >> b; a--; b--;
			g[a].push_back(b);
			g[b].push_back(a);
		}
	}
	Data merge(const Data &lh, const Data &rh) {
		Data ret = lh;
		ret.val0 += rh.max;
		ret.val1 += rh.val0;
		ret.max = max(ret.val0, ret.val1);
		return ret;
	}
	Data mergeR(const Data &lh, const Data &rh) {//★★
		Data ret = lh;
		ret.val0 -= rh.max;
		ret.val1 -= rh.val0;
		ret.max = max(ret.val0, ret.val1);
		return ret;
	}
	void dfs(int v, int p = -1) {
		Data val(0, 1, 1);
		for (auto e : g[v]) {
			if (p == e.to)continue;
			dfs(e.to, v);
			val = merge(val, dp[e.to]);
		}
		dp[v] = val;
	}
	void dfsR(int v, int p = -1) {
		ans[v] = dp[v];
		if (-1 != p)ans[v] = merge(ans[v], dp[p]);
		for (auto e : g[v]) {
			if (p == e.to)continue;
			dp[v] = mergeR(ans[v], dp[e.to]);
			dfsR(e.to, v);
		}
	}
	void output() {
		int val = sz;
		rep(i, sz)chmin(val, ans[i].val1);
		cout << val << endl;
	}
	void solve() {
		ReadGraph();
		dfs(0);
		dfsR(0);
		output();
	}
};
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	ReRooting reroot(n);
	reroot.solve();
	return 0;
}

yukicoder

結果

テストケース

ソースコード