QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#828199#8948. 报复社会chenxinyang20060 48ms9972kbC++231.9kb2024-12-23 14:32:592024-12-23 14:33:01

Judging History

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

  • [2024-12-23 14:33:01]
  • 评测
  • 测评结果:0
  • 用时:48ms
  • 内存:9972kb
  • [2024-12-23 14:32:59]
  • 提交

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 T,n;
int fa[500005],deg[500005],col[500005],a[500005];

set <int> S;
void solve(){
	scanf("%d",&n);
	fill(deg,deg + n + 1,0);
	fill(a,a + n + 1,0);
	rep(u,2,n){
		scanf("%d",&fa[u]);
		deg[fa[u]]++;
	}
	rep(u,1,n) scanf("%d",&col[u]);
	if(n == 1){
		if(!col[1]) printf("Alice\n");
		else printf("Bob\n");
		return;
	}
	rep(u,1,n){
		if(!deg[u]){
			if(!col[u]) a[fa[u]]++;
			else a[fa[u]]--;
		}
	}
	rep(u,1,n) if(fa[u] == 1 && deg[u]) S.insert(a[u]);

//	assert(S.empty());
	int cur = a[1],op = 1;
	while(!S.empty()){
		if(!op){
			if(cur < 0){
				cur++;
			}else{
				auto it = S.begin();
				cur += *it;
				S.erase(it);
			}
		}else{
			if(cur > 0){
				cur--;
			}else{
				auto it = prev(S.end());
				cur += *it;
				S.erase(it);
			}
		}
		op ^= 1;
	}
//	printf("cur=%d\n",cur);
	if(cur > 0 || (!cur && !op)) printf("Alice\n");
	else printf("Bob\n");
}

int main(){
#ifdef cxy
	freopen("test.in","r",stdin);
#endif
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

1
19
1 2 3 3 2 6 7 7 6 6 6 2 2 2 1 1 1 1
0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0

output:

Bob

result:

ok "Bob"

Test #2:

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

input:

1
20
1 1 3 2 4 1 4 4 1 7 1 6 3 12 6 12 8 5 7
1 0 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1

output:

Alice

result:

ok "Alice"

Test #3:

score: 0
Wrong Answer
time: 1ms
memory: 9964kb

input:

1
19
1 2 3 4 5 1 1 8 8 3 7 3 13 3 15 10 2 17
0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0

output:

Bob

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #50:

score: 0
Wrong Answer
time: 48ms
memory: 9900kb

input:

10000
49
1 2 2 1 5 5 5 5 5 5 1 12 12 12 12 12 12 1 19 19 19 19 19 19 19 1 27 27 1 1 31 1 33 33 33 33 33 33 33 1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1
50
1 2 2 2 2 2 1 8 8 8 1 12 1 1 15 15 15 15 1 1 21 21 21 21 1 26 1 1 29 29...

output:

Bob
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Bob
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Alice
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Alice
Bob
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Bob
Alice
Bob
Alice
Bob
Bob
...

result:

wrong answer 3rd words differ - expected: 'Alice', found: 'Bob'

Subtask #3:

score: 0
Wrong Answer

Test #73:

score: 0
Wrong Answer
time: 44ms
memory: 9896kb

input:

10000
50
1 2 1 4 5 6 5 4 9 4 11 4 1 14 15 16 16 16 15 14 21 21 21 14 14 14 14 14 1 30 30 30 30 30 1 36 37 37 37 36 41 41 41 36 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1
50
1 2 3 4 5 4 7 8 7 4 11 12 11 14 11 16 11 18 11 4 21 4 4 4 3 ...

output:

Bob
Bob
Alice
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Bob
Bob
Bob
Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Alice
Alice
Bob
Bob
Bob
Alice
Alice
Alice
Bob
...

result:

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

Subtask #4:

score: 0
Skipped

Dependency #1:

0%