QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#829456#8948. 报复社会275307894a#0 4ms19556kbC++141.9kb2024-12-24 10:10:592024-12-24 10:11:05

Judging History

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

  • [2024-12-24 10:11:05]
  • 评测
  • 测评结果:0
  • 用时:4ms
  • 内存:19556kb
  • [2024-12-24 10:10:59]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=5e5+5,M=(1<<28)+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(28382);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int n,p[N],col[N];
vector<int> S[N];
void Solve(){
	scanf("%d",&n);
	for(int i=2;i<=n;i++) scanf("%d",&p[i]);
	for(int i=1;i<=n;i++) scanf("%d",&col[i]);
	for(int i=2;i<=n;i++) S[p[i]].push_back(i);
	int c1=0,c2=0;
	deque<pii> q;
	for(int i=2;i<=n;i++){
		if(S[i].empty()){
			if(col[i]) c2++;
			else c1++;
			continue;
		}
		q.emplace_back(0,0);
		for(int j:S[i]){
			if(col[j]) q.back().se++;
			else q.back().fi++;
		}
	}
	sort(all(q),[](pii x,pii y){return x.fi-x.se<y.fi-y.se;});
	for(int i=2;i<=n;i++){
		if(i&1){
			if(c2){c2--;continue;}
			if(q.empty()){
				puts("Alice");
				return;
			}
			c1+=q.front().fi;c2+=q.front().se;q.pop_front();
		}else{
			if(c1){c1--;continue;}
			if(q.empty()){
				puts("Bob");
				return;
			}
			c1+=q.back().fi;c2+=q.back().se;q.pop_back();
		}
	}
	puts(n&1?"Bob":"Alice");
}
int main(){
	int t=1;
	scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 20
Accepted
time: 4ms
memory: 19556kb

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: 0ms
memory: 19464kb

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: 4ms
memory: 19032kb

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
Time Limit Exceeded

Test #50:

score: 0
Time Limit Exceeded

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
Alice
Bob
Bob
Alice
Bob
Bob
Alice
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Bob
Alice
Bob
Bob
Alice
Bob
Bob
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Al...

result:


Subtask #3:

score: 0
Time Limit Exceeded

Test #73:

score: 0
Time Limit Exceeded

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:

Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
...

result:


Subtask #4:

score: 0
Skipped

Dependency #1:

0%