結果

問題 No.2800 Game on Tree Inverse
ユーザー shobonvipshobonvip
提出日時 2024-06-26 01:17:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,016 bytes
コンパイル時間 2,888 ms
コンパイル使用メモリ 215,136 KB
実行使用メモリ 150,072 KB
最終ジャッジ日時 2024-06-26 01:17:55
合計ジャッジ時間 27,069 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 726 ms
64,124 KB
testcase_04 WA -
testcase_05 AC 388 ms
108,188 KB
testcase_06 WA -
testcase_07 AC 432 ms
138,008 KB
testcase_08 AC 408 ms
149,240 KB
testcase_09 AC 400 ms
150,072 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 464 ms
86,628 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 553 ms
111,548 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 539 ms
134,408 KB
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 AC 2 ms
6,944 KB
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 WA -
testcase_53 WA -
testcase_54 WA -
testcase_55 WA -
testcase_56 WA -
testcase_57 WA -
testcase_58 WA -
testcase_59 WA -
testcase_60 WA -
testcase_61 WA -
testcase_62 WA -
testcase_63 WA -
testcase_64 WA -
testcase_65 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 


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

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<20>> 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;
			}
		}
		
		for (int j: ikeru[i]){
			if (j == p) continue;
			if (j == mxind) {
				ep[j].xor_all ^= dp[j]^x;
			}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';
	}

}
0