QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#291346#4896. Alice、Bob 与 DFSKevin53070 0ms0kbC++203.1kb2023-12-26 12:43:052023-12-26 12:43:06

Judging History

你现在查看的是最新测评结果

  • [2023-12-26 12:43:06]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-12-26 12:43:05]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int c[400400];
vector<int> G[400400];
int n;
ll g0[400400],g1[400400];
namespace bit
{
	int bit[400400];
	vector<pii> memo;
	void update(int p,int v,bool ign=0)
	{
		if(!ign)
			memo.pb(p,v);
		p++;
		while(p<400400)
		{
			bit[p]+=v;
			p+=(p&(-p));
		}
	}
	int query(int p)
	{
		p++;
		int ans=0;
		while(p)
		{
			ans+=bit[p];
			p-=(p&(-p));
		}
		return ans;
	}
	void clear()
	{
		for(auto pr:memo)
			update(pr.first,-pr.second,1);
		memo.clear();
	}
}
void get()
{
	for(int i=n;i>=1;i--)
		if(c[i])
		{
			rev(G[i]);
			{
				bit::update(0,1);
				for(auto j:G[i]) if(c[j])
				{
					int cur=g0[j];
					int l=0,r=400001;
					while(l<r)
					{
						int mid=(l+r)/2;
						if((mid+1)-bit::query(mid)>=cur)
							r=mid;
						else
							l=mid+1;
					}
					bit::update(l,1);
				}
				else
				{
					int cur=g0[j];
					if(bit::query(cur)==bit::query(cur-1))
						bit::update(cur,1);
				}
				int l=0,r=400001;
				while(l<r)
				{
					int mid=(l+r)/2;
					if((mid+1)-bit::query(mid))
						r=mid;
					else
						l=mid+1;
				}
				g0[i]=l;
				bit::clear();
			}
			{
				for(auto j:G[i]) if(c[j])
				{
					int cur=(bit::query(0)?g0[j]:g1[j]+1);
					int l=0,r=400001;
					while(l<r)
					{
						int mid=(l+r)/2;
						if((mid+1)-bit::query(mid)>=cur)
							r=mid;
						else
							l=mid+1;
					}
					bit::update(l,1);
				}
				else
				{
					int cur=(bit::query(0)?g0[j]:g1[j]);
					if(bit::query(cur)==bit::query(cur-1))
						bit::update(cur,1);
				}
				int l=0,r=400001;
				while(l<r)
				{
					int mid=(l+r)/2;
					if((mid+1)-bit::query(mid))
						r=mid;
					else
						l=mid+1;
				}
				g1[i]=l;
				bit::clear();
			}
		}
		else
		{
			int cur0=0,cur1=1;
			rev(G[i]);
			for(auto j:G[i])
			{
				cur0=(cur0?g1[j]:g0[j]);
				cur1=(cur1?g1[j]:g0[j]);
			}
			g0[i]=cur0^1;
			g1[i]=cur1^1;
		}
}
int main()
{
	freopen("Genshin_lmpact.in","r",stdin);
	freopen("Genshin_lmpact.out","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>c[i];
	for(int i=1;i<=n;i++)
	{
		int m;
		cin>>m;
		if(!m) c[i]=1;
		while(m--)
		{
			int x;
			cin>>x;
			G[i].pb(x);
		}
	}
	get();
//	for(int i=1;i<=n;i++)
//		cerr<<g0[i]<<" "<<g1[i]<<endl;
	int k;
	cin>>k;
	int ans=0;
	while(k--)
	{
		int x;
		cin>>x;
		ans^=g0[x];
	}
	if(ans)
		cout<<"Alice";
	else
		cout<<"Bob";
	return 0;
}

詳細信息

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

input:

1000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:


result:


Subtask #2:

score: 0
Dangerous Syscalls

Test #18:

score: 0
Dangerous Syscalls

input:

7
0 0 1 1 0 1 1
1 2
2 3 4
0
2 5 6
0
1 7
0
1
1

output:


result:


Subtask #3:

score: 0
Dangerous Syscalls

Test #55:

score: 0
Dangerous Syscalls

input:

7
0 0 1 1 0 1 1
1 2
2 3 4
0
2 5 6
0
1 7
0
1
1

output:


result:


Subtask #4:

score: 0
Dangerous Syscalls

Test #103:

score: 0
Dangerous Syscalls

input:

10
1 1 1 1 1 1 1 1 1 1
1 2
4 3 5 7 8
1 4
0
1 6
0
0
1 9
1 10
0
1
1

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%