結果
問題 | No.2800 Game on Tree Inverse |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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":" "); }