結果

問題 No.2800 Game on Tree Inverse
コンテスト
ユーザー kotatsugame
提出日時 2024-06-28 22:22:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 605 ms / 4,000 ms
コード長 1,996 bytes
コンパイル時間 1,187 ms
コンパイル使用メモリ 89,164 KB
実行使用メモリ 111,972 KB
最終ジャッジ日時 2024-06-28 22:22:51
合計ジャッジ時間 18,814 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 64
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<algorithm>
#include<vector>
#include<array>
#include<set>
#include<cassert>
using namespace std;
const int sz=20;
struct binarytrie{
	using Bit=unsigned int;
	struct node{
		int cnt;
		array<int,2>nxt;
		node():cnt(0),nxt({-1,-1}){}
	};
	vector<node>v;
	set<Bit>EX;
	Bit XOR;
	binarytrie():XOR(0u),EX(){v.emplace_back();}
	void Xor(Bit x){XOR^=x;}
	void insert(Bit x)
	{
		x^=XOR;
		assert(0<=x&&(x>>sz)==0);
		if(EX.find(x)!=EX.end())return;
		EX.insert(x);
		int p=0;
		v[p].cnt++;
		for(int i=sz;i--;)
		{
			int j=x>>i&1;
			if(v[p].nxt[j]==-1)
			{
				v[p].nxt[j]=v.size();
				v.emplace_back();
			}
			p=v[p].nxt[j];
			v[p].cnt++;
		}
	}
	Bit mex()const
	{
		int p=0;
		Bit ret=0;
		for(int i=sz;i--;)
		{
			int need=1<<i;
			int j=XOR>>i&1;
			if(v[p].nxt[j]==-1)return ret;
			else if(v[v[p].nxt[j]].cnt<need)p=v[p].nxt[j];
			else
			{
				ret|=1<<i;
				if(v[p].nxt[!j]==-1)return ret;
				p=v[p].nxt[!j];
			}
		}
		return ret;
	}
	void swap(binarytrie&rhs)
	{
		v.swap(rhs.v);
		EX.swap(rhs.EX);
		std::swap(XOR,rhs.XOR);
	}
};
int N;
vector<int>G[2<<17];
binarytrie ret;
int gru[2<<17];
void dfs(int u,int p)
{
	int all=0;
	binarytrie cur;
	cur.insert(0);
	for(int v:G[u])if(v!=p)
	{
		dfs(v,u);
		ret.Xor(all);
		all^=gru[v];
		cur.Xor(gru[v]);
		if(cur.EX.size()<ret.EX.size())cur.swap(ret);
		for(unsigned int b:ret.EX)
		{
			b^=ret.XOR;
			cur.insert(b);
		}
	}
	gru[u]=cur.mex();
	ret.swap(cur);
}
vector<int>X;
void dfs2(int u,int p,int cur)
{
	for(int v:G[u])if(v!=p)cur^=gru[v];
	if(cur==0)X.push_back(u);
	for(int v:G[u])if(v!=p)dfs2(v,u,cur^gru[v]);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N;
	for(int i=1;i<N;i++)
	{
		int u,v;cin>>u>>v;u--,v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(0,-1);
	if(gru[0]==0)
	{
		cout<<"Bob"<<endl;
		return 0;
	}
	cout<<"Alice\n";
	dfs2(0,-1,0);
	cout<<X.size()<<"\n";
	sort(X.begin(),X.end());
	for(int i=0;i<X.size();i++)cout<<X[i]+1<<(i+1==X.size()?"\n":" ");
}
0