#991533 (C++14) No.2800 Game on Tree Inverse

提出ソース

結果

問題	No.2800 Game on Tree Inverse
ユーザー	kotatsugame
提出日時	2024-06-28 22:22:22
言語	C++14 (gcc 12.3.0 + boost 1.83.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

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	6 ms 9,472 KB
testcase_01	AC	6 ms 9,600 KB
testcase_02	AC	6 ms 9,600 KB
testcase_03	AC	605 ms 108,500 KB
testcase_04	AC	284 ms 16,640 KB
testcase_05	AC	284 ms 16,640 KB
testcase_06	AC	276 ms 17,536 KB
testcase_07	AC	274 ms 17,920 KB
testcase_08	AC	245 ms 17,792 KB
testcase_09	AC	248 ms 17,260 KB
testcase_10	AC	403 ms 20,412 KB
testcase_11	AC	470 ms 84,632 KB
testcase_12	AC	477 ms 47,820 KB
testcase_13	AC	333 ms 17,280 KB
testcase_14	AC	325 ms 17,280 KB
testcase_15	AC	484 ms 70,644 KB
testcase_16	AC	328 ms 17,408 KB
testcase_17	AC	477 ms 66,060 KB
testcase_18	AC	410 ms 17,152 KB
testcase_19	AC	259 ms 16,840 KB
testcase_20	AC	479 ms 62,968 KB
testcase_21	AC	360 ms 17,104 KB
testcase_22	AC	302 ms 16,788 KB
testcase_23	AC	408 ms 47,364 KB
testcase_24	AC	381 ms 63,540 KB
testcase_25	AC	337 ms 16,896 KB
testcase_26	AC	274 ms 16,512 KB
testcase_27	AC	398 ms 72,776 KB
testcase_28	AC	249 ms 16,716 KB
testcase_29	AC	508 ms 60,508 KB
testcase_30	AC	335 ms 18,880 KB
testcase_31	AC	305 ms 19,068 KB
testcase_32	AC	568 ms 111,972 KB
testcase_33	AC	381 ms 53,688 KB
testcase_34	AC	343 ms 54,284 KB
testcase_35	AC	470 ms 53,976 KB
testcase_36	AC	7 ms 9,600 KB
testcase_37	AC	7 ms 9,600 KB
testcase_38	AC	7 ms 9,600 KB
testcase_39	AC	7 ms 9,472 KB
testcase_40	AC	7 ms 9,472 KB
testcase_41	AC	8 ms 9,472 KB
testcase_42	AC	7 ms 9,472 KB
testcase_43	AC	7 ms 9,344 KB
testcase_44	AC	7 ms 9,600 KB
testcase_45	AC	7 ms 9,600 KB
testcase_46	AC	7 ms 9,600 KB
testcase_47	AC	9 ms 9,856 KB
testcase_48	AC	9 ms 9,600 KB
testcase_49	AC	18 ms 10,240 KB
testcase_50	AC	13 ms 9,984 KB
testcase_51	AC	205 ms 16,128 KB
testcase_52	AC	21 ms 10,368 KB
testcase_53	AC	45 ms 11,264 KB
testcase_54	AC	192 ms 15,592 KB
testcase_55	AC	353 ms 18,840 KB
testcase_56	AC	266 ms 17,004 KB
testcase_57	AC	370 ms 19,672 KB
testcase_58	AC	120 ms 13,696 KB
testcase_59	AC	162 ms 14,124 KB
testcase_60	AC	121 ms 13,440 KB
testcase_61	AC	84 ms 12,544 KB
testcase_62	AC	115 ms 13,056 KB
testcase_63	AC	126 ms 13,468 KB
testcase_64	AC	50 ms 11,520 KB
testcase_65	AC	50 ms 11,648 KB

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

ソースコード

raw source code

#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":" ");
}

yukicoder

結果

テストケース

ソースコード