結果

問題 No.768 Tapris and Noel play the game on Treeone
ユーザー pekempey
提出日時 2018-12-16 02:23:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,465 bytes
コンパイル時間 936 ms
コンパイル使用メモリ 84,308 KB
実行使用メモリ 9,208 KB
最終ジャッジ日時 2024-09-25 06:21:50
合計ジャッジ時間 3,259 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other AC * 1 WA * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/vector:65,
                 from main.cpp:3:
In member function 'std::_Bit_reference& std::_Bit_reference::operator=(bool)',
    inlined from 'free_tree_dp<bool, main()::<lambda(bool, bool)>, main()::<lambda(bool)> >(const std::vector<std::vector<int> >&, main()::<lambda(bool, bool)>, main()::<lambda(bool)>)::<lambda(int, int)>' at main.cpp:41:9:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_bvector.h:102:7: warning: 'l' may be used uninitialized [-Wmaybe-uninitialized]
  102 |       if (__x)
      |       ^~
main.cpp: In lambda function:
main.cpp:28:19: note: 'l' was declared here
   28 |                 T l;
      |                   ^

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>

using namespace std;

// add :: T -> T -> T
//     {v1,v2,...,vm}+vm+1
// bundle :: T -> T
//     u->{v1,v2,v3,...,vm} 
template<class T, class F1, class F2>
vector<T> free_tree_dp(const vector<vector<int>> &g, F1 add, F2 bundle) {
	const int n = g.size();
	vector<T> dp(n);
	function<void(int, int)> dfs = [&](int u, int p) {
		for (int v : g[u]) {
			if (v != p) {
				dfs(v, u);
				dp[u] = add(dp[u], dp[v]);
			}
		}
		dp[u] = bundle(dp[u]);
	};
	dfs(0, -1);
	function<void(int, int)> dfs2 = [&](int u, int p) {
		const int m = g[u].size();
		T l;
		vector<T> r(m);
		for (int i = m - 2; i >= 0; i--) {
			r[i] = add(dp[g[u][i + 1]], r[i + 1]);
		}
		for (int i = 0; i < m; i++) {
			const int v = g[u][i];
			dp[u] = bundle(add(l, r[i]));
			l = add(l, dp[v]);
			if (v != p) {
				dfs2(v, u);
			}
		}
		dp[u] = bundle(l);
	};
	dfs2(0, -1);
	return dp;
}

int main() {
	int n;
	cin >> n;
	vector<vector<int>> g(n);
	for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
		u--;
		v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	auto add = [&](bool a, bool b) {
        return a || b;
	};
	auto bundle = [&](bool a) {
        return !a;
	};
    auto dp = free_tree_dp<bool>(g, add, bundle);
    cout << count(dp.begin(), dp.end(), true) << endl;
    for (int i = 0; i < n; i++) {
        if (dp[i]) {
            cout << i + 1 << endl;
        }
    }
}
0