QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#407914#4896. Alice、Bob 与 DFSchenxinyang20060 2ms5416kbC++202.4kb2024-05-09 14:40:432024-05-09 14:40:45

Judging History

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

  • [2024-05-09 14:40:45]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:5416kb
  • [2024-05-09 14:40:43]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n;
int a[200005];
vector <int> ch[200005];

int N = 1,tree[400005],tp[400005],_cur;
#define lowbit(x) (x & (-x))
void fix(int pos){
	if(tp[pos] > _cur) tree[pos] = 0;
	tp[pos] = _cur;	
}
void upd(int pos,int C){
	while(pos <= N){
		fix(pos);
		tree[pos] += C;
		pos += lowbit(pos);
	}
}

int qry(int pos){
	int ret = 0;
	while(pos){
		fix(pos);
		ret += tree[pos];
		pos -= lowbit(pos);
	}
	return ret;
}

int kth(int k){
	int pos = 0;
	per(_k,17,0){
		if(pos + (1 << _k) <= N){
			fix(pos + (1 << _k));
			if(k > (1 << _k) - tree[pos + (1 << _k)]){
				pos += 1 << _k;
				k -= (1 << _k) - tree[pos];
			}
		}
	}
	return pos + 1;
}

int dp[200005][4];
void solve2(int u){//u 是白点
	_cur = u;
	rep(S,0,3){
		int cur = S,temp;
		for(int v:ch[u]){
			temp = dp[v][cur];
			if(temp <= 1) cur |= (1 << temp);
			else upd(kth(temp),1);
		}
		if((cur & 1) == 0) dp[u][S] = 0;
		else if((cur & 2) == 0) dp[u][S] = 1;
		else dp[u][S] = kth(2);
 	}
}

void solve1(int u){
	assert(0);
}

int main(){
//	freopen("test.in","r",stdin);
	scanf("%d",&n);
	rep(u,1,n) scanf("%d",&a[u]);
	rep(u,1,n){
		int sz;
		scanf("%d",&sz);
		N += sz;
		ch[u].resize(sz);
		rep(j,0,sz - 1) scanf("%d",&ch[u][j]);
		reverse(ch[u].begin(),ch[u].end());
	}

	memset(tp,0x3f,sizeof(tp));
	per(u,n,1){
		if(!a[u]) solve1(u);
		else solve2(u);
	}

	int k,id,answer = 0;
	scanf("%d",&k);
	while(k--){
		scanf("%d",&id);
		answer ^= dp[id][1];
	}
	if(!answer) printf("Bob\n");
	else printf("Alice\n");
	return 0;
}

詳細信息

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

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
Runtime Error

Test #18:

score: 0
Runtime Error

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
Runtime Error

Test #55:

score: 0
Runtime Error

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
Wrong Answer

Test #103:

score: 20
Accepted
time: 2ms
memory: 5412kb

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:

Alice

result:

ok "Alice"

Test #104:

score: 20
Accepted
time: 0ms
memory: 5272kb

input:

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

output:

Alice

result:

ok "Alice"

Test #105:

score: 20
Accepted
time: 1ms
memory: 5316kb

input:

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

output:

Alice

result:

ok "Alice"

Test #106:

score: 20
Accepted
time: 2ms
memory: 5352kb

input:

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

output:

Alice

result:

ok "Alice"

Test #107:

score: 20
Accepted
time: 1ms
memory: 5380kb

input:

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

output:

Alice

result:

ok "Alice"

Test #108:

score: 20
Accepted
time: 0ms
memory: 5276kb

input:

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

output:

Bob

result:

ok "Bob"

Test #109:

score: 20
Accepted
time: 1ms
memory: 5380kb

input:

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

output:

Bob

result:

ok "Bob"

Test #110:

score: 20
Accepted
time: 1ms
memory: 5268kb

input:

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

output:

Bob

result:

ok "Bob"

Test #111:

score: 20
Accepted
time: 1ms
memory: 5380kb

input:

100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 2
1 3
2 4 38
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
4 14 35 36 37
1 15
1 16
1 17
1 18
2 19 31...

output:

Alice

result:

ok "Alice"

Test #112:

score: 0
Wrong Answer
time: 0ms
memory: 5416kb

input:

100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 2
0
2 4 29
1 5
3 6 7 8
0
0
1 9
1 10
5 11 20 21 27 28
5 12 13 16 18 19
0
2 14 15
0
0
1 17
0
0
0...

output:

Alice

result:

wrong answer 1st words differ - expected: 'Bob', found: 'Alice'

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%