#990831 (C++17) No.2800 Game on Tree Inverse

提出ソース

結果

問題	No.2800 Game on Tree Inverse
ユーザー	shobonvip
提出日時	2024-06-26 01:24:01
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	790 ms / 4,000 ms
コード長	4,333 bytes
コンパイル時間	3,182 ms
コンパイル使用メモリ	215,460 KB
実行使用メモリ	137,648 KB
最終ジャッジ日時	2024-06-26 01:24:31
合計ジャッジ時間	24,446 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	790 ms 63,852 KB
testcase_04	AC	366 ms 81,720 KB
testcase_05	AC	380 ms 99,904 KB
testcase_06	AC	372 ms 109,812 KB
testcase_07	AC	365 ms 126,888 KB
testcase_08	AC	400 ms 136,860 KB
testcase_09	AC	371 ms 137,648 KB
testcase_10	AC	423 ms 78,100 KB
testcase_11	AC	648 ms 114,112 KB
testcase_12	AC	547 ms 98,160 KB
testcase_13	AC	397 ms 93,816 KB
testcase_14	AC	415 ms 101,080 KB
testcase_15	AC	605 ms 107,252 KB
testcase_16	AC	497 ms 101,568 KB
testcase_17	AC	734 ms 87,924 KB
testcase_18	AC	370 ms 84,928 KB
testcase_19	AC	342 ms 91,744 KB
testcase_20	AC	625 ms 95,980 KB
testcase_21	AC	414 ms 94,580 KB
testcase_22	AC	370 ms 100,956 KB
testcase_23	AC	514 ms 93,272 KB
testcase_24	AC	471 ms 82,428 KB
testcase_25	AC	356 ms 82,104 KB
testcase_26	AC	378 ms 92,604 KB
testcase_27	AC	536 ms 105,856 KB
testcase_28	AC	396 ms 109,672 KB
testcase_29	AC	556 ms 71,316 KB
testcase_30	AC	360 ms 80,140 KB
testcase_31	AC	416 ms 108,104 KB
testcase_32	AC	678 ms 97,684 KB
testcase_33	AC	493 ms 99,084 KB
testcase_34	AC	498 ms 126,948 KB
testcase_35	AC	532 ms 97,256 KB
testcase_36	AC	2 ms 6,940 KB
testcase_37	AC	2 ms 6,940 KB
testcase_38	AC	2 ms 6,940 KB
testcase_39	AC	2 ms 6,940 KB
testcase_40	AC	2 ms 6,940 KB
testcase_41	AC	2 ms 6,940 KB
testcase_42	AC	2 ms 6,940 KB
testcase_43	AC	2 ms 6,944 KB
testcase_44	AC	2 ms 6,944 KB
testcase_45	AC	2 ms 6,940 KB
testcase_46	AC	2 ms 6,940 KB
testcase_47	AC	4 ms 6,940 KB
testcase_48	AC	4 ms 6,940 KB
testcase_49	AC	15 ms 6,940 KB
testcase_50	AC	9 ms 6,940 KB
testcase_51	AC	224 ms 44,724 KB
testcase_52	AC	17 ms 7,168 KB
testcase_53	AC	42 ms 12,800 KB
testcase_54	AC	200 ms 44,032 KB
testcase_55	AC	372 ms 68,248 KB
testcase_56	AC	264 ms 55,612 KB
testcase_57	AC	372 ms 75,056 KB
testcase_58	AC	128 ms 30,464 KB
testcase_59	AC	199 ms 38,400 KB
testcase_60	AC	144 ms 27,776 KB
testcase_61	AC	83 ms 21,120 KB
testcase_62	AC	120 ms 28,800 KB
testcase_63	AC	135 ms 32,128 KB
testcase_64	AC	51 ms 14,720 KB
testcase_65	AC	50 ms 14,592 KB

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

ソースコード

raw source code


#include<bits/stdc++.h>
using namespace std;

/*

STEP 1: 木DPですべての部分木についての grundy 数を求める.
この後で, 問題の要求に答えることは相対的に簡単である.

STEP 2: 木DPで持つべきは,
1. dp[i] := i の部分木の grundy 数
2. ep[i] := i の部分木であって, 頂点 i をパスに使用している場合の grundy 数の集合.

更新について:
i の子の集合を S とする.
X = xor {dp[j] | j∈S} としよう.
F = ∪[j∈S]{e^dp[j]^X | e ∈ ep[j]} ∪ {X} とする.
ep[i] は F, dp[i] は mex{F}.

ep[i] の要素数が最大で数十万になることから, ここが律速であると間に合わない.
この問題の真の姿は, ep[i] を高速に管理するデータ構造を考える問題である.
要素の追加・全部にxor・mex が高速にできるデータ構造を用意すれば,
そのまま「マージテク」の形をしているので解決できる.

そして, そのデータ構造として適しているのは, binary trie である.
mex はやや厄介だが, 「x番目の要素はxである」を満たす最大のxを二分探索で求めればよい.
mex は頻繁に呼ばれないため, ここは少し遅くても問題ない. (実際 mex の部分は O(N log^2 N) 時間)

time : O(N log^2 N)
space : O(N log N)

*/

template <int MAX_LOG>
struct binary_trie {
	struct node {
		node *ch[2] = {nullptr, nullptr};
		int cnt = 0;
		node() {}
	};

	public:
		node *root = nullptr;
		int xor_all = 0;
		binary_trie() : root(nullptr) {}

		void insert(int val){
			val ^= xor_all;
			root = insert(root, val);
		}
		
		int count(int val){
			node* now_node = root;
			val ^= xor_all;
			for (int b=MAX_LOG-1; b>=0; b--){
				if (now_node == nullptr) break;
				now_node = now_node->ch[(val>>b)&1];
			}
			return size(now_node);
		}
		
		int xth(int x){
			node* now_node = root;
			assert(now_node != nullptr);
			int ret = 0;
			for (int b=MAX_LOG-1; b>=0; b--){
				bool f = (xor_all>>b)&1;
				if (size(now_node->ch[f]) <= x){
					x -= size(now_node->ch[f]);
					now_node = now_node->ch[f^1];
					ret = (ret<<1)|(f^1);
				}else{
					assert(1 <= size(now_node->ch[f]));
					now_node = now_node->ch[f];
					ret = (ret<<1)|f;
				}
			}
			return ret ^ xor_all;
		}

		int mex(){
			int ub = root->cnt;
			int lb = -1;
			while (ub - lb > 1){
				int t = (ub + lb) / 2;
				if (xth(t) == t) lb = t;
				else ub = t;
			}
			return lb + 1;
		}

	private:
		node* insert(node* t, int val, int b = MAX_LOG - 1){
			if (t == nullptr) t = new node;
			t->cnt++;
			if (b < 0) return t;
			bool f = (val>>b)&1;
			t->ch[f] = insert(t->ch[f], val, b-1);
			return t;
		}

		int size(node* t){
			if (t == nullptr) return 0;
			return t->cnt;
		}

};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n; cin >> n;
	vector<vector<int>> ikeru(n, vector<int>(0));
	for (int i=0; i<n-1; i++){
		int u, v; cin >> u >> v;
		u--; v--;
		ikeru[u].push_back(v);
		ikeru[v].push_back(u);
	}

	vector<int> dp(n);
	vector<binary_trie<18>> ep(n);

	auto dfs1 = [&](auto self, int i, int p) -> void {
		int x = 0;
		int mxval = 0;
		int mxind = i;
		for (int j: ikeru[i]){
			if (j == p) continue;
			self(self, j, i);
			x ^= dp[j];
			if (mxval < ep[j].root->cnt) {
				mxval = ep[j].root->cnt;
				mxind = j;
			}
		}
		
		ep[mxind].xor_all ^= dp[mxind]^x;
		
		for (int j: ikeru[i]){
			if (j == p) continue;
			if (j == mxind) {
				continue;
			}else{
				int mxz = ep[j].root->cnt;
				for (int z=0; z<mxz; z++){
					int tar = ep[j].xth(z);
					if (ep[mxind].count(tar^x^dp[j]) == 0){
						ep[mxind].insert(tar^x^dp[j]);
					}
				}	
			}
		}
		
		if (ep[mxind].count(x) == 0){
			ep[mxind].insert(x);
		}

		swap(ep[mxind], ep[i]);
		dp[i] = ep[i].mex();
	};

	dfs1(dfs1, 0, -1);

	vector<int> ans;
	auto dfs2 = [&](auto self, int i, int p, int g) -> void {
		int x = g;
		for (int j: ikeru[i]){
			if (j == p) continue;
			x ^= dp[j];
		}

		if (x == 0) ans.push_back(i);

		for (int j: ikeru[i]){
			if (j == p) continue;
			self(self, j, i, x^dp[j]);
		}
	};

	dfs2(dfs2, 0, -1, 0);

	if (ans.empty()){
		cout << "Bob\n";
	}else{
		cout << "Alice\n";
		int k = ans.size();
		sort(ans.begin(), ans.end());
		cout << k << '\n';
		for (int x: ans){
			cout << x+1 << ' ';
		}
		cout << '\n';
	}

}

yukicoder

結果

テストケース

ソースコード