QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#792392 | #8948. 报复社会 | misfits# | 20 | 188ms | 28216kb | C++14 | 1.9kb | 2024-11-29 09:51:46 | 2024-11-29 09:51:47 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define SZ(x) ((LL)(x.size()))
#define all(x) (x).begin(),(x).end()
using namespace std;
inline LL read(){
LL q=0,w=1;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){q=q*10+(ch-'0');ch=getchar();}
return q*w;
}
void write(LL x){
if(x<0){putchar('-');x=(-x);}
if(x>9)write(x/10);
putchar('0'+x%10);
}
inline void writeln(LL x){write(x);puts("");}
inline void writecs(LL x){write(x);putchar(' ');}
inline void dmin(LL &x,LL y){if(x>y)x=y;return ;}
inline void dmax(LL &x,LL y){if(x<y)x=y;return ;}
#define cout cerr
#define pb push_back
const LL N = 500000+95 ;
LL n,fa[N],col[N];vector<LL>E[N];
namespace sub1{
map<vector<LL>,LL>MP;
LL dfs(vector<LL>x,LL op){//op=0:Alice操作;op=1:Bob操作.
sort(all(x));
if(MP.find(x)!=MP.end())return MP[x];
LL ok[2]={0,0};
for(auto u:x){
vector<LL>y;for(auto v:x)if(u!=v)y.pb(v);
for(auto v:E[u])y.pb(v);
if(!SZ(y))return col[u];
ok[dfs(y,op^1)]=1;
}
if(op==0){LL u=((ok[0])?(0):(1));MP[x]=u;return u;}
if(op==1){LL u=((ok[1])?(1):(0));MP[x]=u;return u;}
}
void solve(){
MP.clear();LL ans=dfs({1},0);
if(!ans)puts("Alice");
else puts("Bob");
return ;
}
}
namespace sub2{
bool check(){
for(LL t=1;t<=n;t++){
if(t==1)continue;
if(fa[t]==1)continue;
if(fa[fa[t]]==1)continue;
return 0;
}
return 1;
}
void solve(){
return ;
}
}
int main(){
LL TC=read();
while(TC--){
n=read();
for(LL t=1;t<=n;t++)E[t].clear();
for(LL t=2;t<=n;t++){fa[t]=read();E[fa[t]].pb(t);}
for(LL t=1;t<=n;t++)col[t]=read();
if(n<=20){
sub1::solve();
continue;
}
if(sub2::check()){
sub2::solve();
continue;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 70ms
memory: 21624kb
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: 23ms
memory: 20940kb
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: 20
Accepted
time: 7ms
memory: 19440kb
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:
Alice
result:
ok "Alice"
Test #4:
score: 20
Accepted
time: 5ms
memory: 19472kb
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:
Alice
result:
ok "Alice"
Test #5:
score: 20
Accepted
time: 18ms
memory: 18444kb
input:
1 19 1 1 1 1 1 3 4 7 3 2 8 6 2 10 10 4 7 14 0 0 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1
output:
Bob
result:
ok "Bob"
Test #6:
score: 20
Accepted
time: 44ms
memory: 21820kb
input:
1 20 1 2 3 4 5 3 7 3 3 3 2 2 2 1 15 16 16 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 1 1 1
output:
Alice
result:
ok "Alice"
Test #7:
score: 20
Accepted
time: 21ms
memory: 19220kb
input:
1 19 1 2 3 4 2 2 2 1 9 10 11 11 10 10 10 9 17 9 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1
output:
Alice
result:
ok "Alice"
Test #8:
score: 20
Accepted
time: 94ms
memory: 22860kb
input:
1 20 1 2 3 4 4 3 3 2 9 10 9 9 9 9 9 2 2 2 2 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 1 1 1 1
output:
Alice
result:
ok "Alice"
Test #9:
score: 20
Accepted
time: 24ms
memory: 19948kb
input:
1 19 1 2 3 4 5 6 6 5 9 5 5 5 2 2 2 2 2 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1
output:
Alice
result:
ok "Alice"
Test #10:
score: 20
Accepted
time: 24ms
memory: 19396kb
input:
1 20 1 2 2 2 3 1 6 4 3 2 8 2 5 7 3 3 10 10 15 0 1 1 0 0 0 1 0 1 1 1 0 0 0 0 1 1 0 0 0
output:
Alice
result:
ok "Alice"
Test #11:
score: 20
Accepted
time: 10ms
memory: 19432kb
input:
1 19 1 2 3 1 4 6 2 8 6 4 3 6 10 7 6 3 5 2 1 0 1 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0
output:
Alice
result:
ok "Alice"
Test #12:
score: 20
Accepted
time: 28ms
memory: 20888kb
input:
1 20 1 1 3 2 2 4 4 6 5 1 5 2 2 10 13 11 6 5 11 1 1 0 0 0 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0
output:
Alice
result:
ok "Alice"
Test #13:
score: 20
Accepted
time: 10ms
memory: 19504kb
input:
1 19 1 2 3 1 4 6 6 1 4 10 5 3 7 11 4 4 4 4 1 0 1 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 0
output:
Alice
result:
ok "Alice"
Test #14:
score: 20
Accepted
time: 47ms
memory: 20808kb
input:
1 20 1 2 3 4 5 5 3 8 3 3 3 3 2 14 15 2 2 2 2 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 1
output:
Alice
result:
ok "Alice"
Test #15:
score: 20
Accepted
time: 47ms
memory: 21208kb
input:
1 20 1 2 3 4 5 5 3 8 3 3 3 3 2 14 15 2 2 2 2 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 1
output:
Alice
result:
ok "Alice"
Test #16:
score: 20
Accepted
time: 19ms
memory: 19096kb
input:
1 19 1 2 3 4 5 3 3 3 3 2 1 12 13 12 15 15 15 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 1
output:
Bob
result:
ok "Bob"
Test #17:
score: 20
Accepted
time: 140ms
memory: 24872kb
input:
1 19 1 2 3 3 1 6 6 6 6 6 6 6 6 6 6 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 0
output:
Bob
result:
ok "Bob"
Test #18:
score: 20
Accepted
time: 101ms
memory: 23072kb
input:
1 20 1 2 3 4 5 5 5 4 4 4 4 4 3 3 2 2 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0
output:
Bob
result:
ok "Bob"
Test #19:
score: 20
Accepted
time: 12ms
memory: 18780kb
input:
1 19 1 2 3 1 5 1 6 1 6 6 1 4 7 13 2 14 10 2 0 0 1 0 1 1 1 0 1 0 0 0 0 0 0 0 1 1 0
output:
Alice
result:
ok "Alice"
Test #20:
score: 20
Accepted
time: 6ms
memory: 19204kb
input:
1 20 1 1 3 1 2 5 7 6 8 3 8 4 9 4 12 7 17 7 16 0 1 1 0 1 1 0 1 1 1 0 1 0 0 1 0 1 1 1 1
output:
Bob
result:
ok "Bob"
Test #21:
score: 20
Accepted
time: 21ms
memory: 20436kb
input:
1 19 1 1 1 1 3 6 1 5 2 4 2 8 2 1 9 14 10 8 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0
output:
Bob
result:
ok "Bob"
Test #22:
score: 20
Accepted
time: 117ms
memory: 23768kb
input:
1 20 1 2 3 4 4 4 3 8 8 8 8 3 3 3 3 3 2 2 2 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 1 1 0 0 1
output:
Bob
result:
ok "Bob"
Test #23:
score: 20
Accepted
time: 7ms
memory: 19248kb
input:
1 19 1 1 2 3 4 2 1 1 1 6 7 6 3 5 5 16 15 12 0 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 0 1 0
output:
Bob
result:
ok "Bob"
Test #24:
score: 20
Accepted
time: 134ms
memory: 24752kb
input:
1 20 1 2 3 4 4 4 4 3 9 9 3 3 2 2 2 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 1 0 1
output:
Alice
result:
ok "Alice"
Test #25:
score: 20
Accepted
time: 10ms
memory: 19500kb
input:
1 19 1 1 2 3 2 6 6 4 3 8 10 2 11 9 5 1 10 5 1 1 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0
output:
Bob
result:
ok "Bob"
Test #26:
score: 20
Accepted
time: 29ms
memory: 19680kb
input:
1 20 1 2 2 4 4 4 1 6 4 10 9 6 2 2 4 5 9 12 8 0 1 0 1 0 1 0 0 1 1 1 1 0 0 1 1 0 1 0 1
output:
Alice
result:
ok "Alice"
Test #27:
score: 20
Accepted
time: 6ms
memory: 18064kb
input:
1 19 1 1 1 3 5 2 3 2 1 7 6 11 12 9 13 7 16 15 0 0 1 0 1 1 1 0 0 0 1 0 1 0 1 0 0 0 1
output:
Alice
result:
ok "Alice"
Test #28:
score: 20
Accepted
time: 21ms
memory: 19868kb
input:
1 20 1 2 3 2 4 4 2 7 2 5 8 8 1 9 1 3 3 9 5 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 0
output:
Alice
result:
ok "Alice"
Test #29:
score: 20
Accepted
time: 7ms
memory: 18300kb
input:
1 19 1 2 3 4 5 6 2 8 2 2 2 2 1 14 15 16 15 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1
output:
Alice
result:
ok "Alice"
Test #30:
score: 20
Accepted
time: 11ms
memory: 20124kb
input:
1 19 1 2 3 4 5 6 2 8 2 2 2 2 1 14 15 16 15 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1
output:
Alice
result:
ok "Alice"
Test #31:
score: 20
Accepted
time: 49ms
memory: 21672kb
input:
1 19 1 2 2 2 1 6 7 8 8 8 8 8 6 6 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0
output:
Alice
result:
ok "Alice"
Test #32:
score: 20
Accepted
time: 45ms
memory: 21280kb
input:
1 20 1 2 3 4 5 6 5 3 9 9 9 3 2 2 2 2 2 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 0 1
output:
Alice
result:
ok "Alice"
Test #33:
score: 20
Accepted
time: 54ms
memory: 21040kb
input:
1 19 1 2 2 2 2 1 7 8 9 8 8 7 13 7 7 1 1 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 1 1 0 1
output:
Bob
result:
ok "Bob"
Test #34:
score: 20
Accepted
time: 70ms
memory: 21280kb
input:
1 20 1 2 1 4 5 6 5 4 9 10 10 9 9 9 9 9 4 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1
output:
Alice
result:
ok "Alice"
Test #35:
score: 20
Accepted
time: 16ms
memory: 18688kb
input:
1 19 1 2 2 4 2 1 5 6 1 5 4 12 9 2 9 9 12 4 1 0 1 1 1 1 1 0 0 1 1 1 1 0 1 0 1 0 1
output:
Bob
result:
ok "Bob"
Test #36:
score: 20
Accepted
time: 188ms
memory: 28216kb
input:
1 20 1 2 3 4 5 4 3 3 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1
output:
Alice
result:
ok "Alice"
Test #37:
score: 20
Accepted
time: 18ms
memory: 18972kb
input:
1 19 1 2 3 4 2 6 7 6 6 2 2 1 13 14 14 13 13 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1
output:
Alice
result:
ok "Alice"
Test #38:
score: 20
Accepted
time: 3ms
memory: 17848kb
input:
1 20 1 2 3 4 1 3 7 6 5 8 8 5 11 12 9 9 8 14 6 1 1 0 1 1 1 0 1 1 1 0 0 0 0 1 1 0 1 1 0
output:
Bob
result:
ok "Bob"
Test #39:
score: 20
Accepted
time: 102ms
memory: 23868kb
input:
1 19 1 2 3 4 4 4 4 3 3 3 3 2 2 2 2 1 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 1
output:
Bob
result:
ok "Bob"
Test #40:
score: 20
Accepted
time: 111ms
memory: 24732kb
input:
1 20 1 2 3 4 3 6 7 3 2 10 2 2 2 2 2 1 1 1 1 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0
output:
Bob
result:
ok "Bob"
Test #41:
score: 20
Accepted
time: 107ms
memory: 24248kb
input:
1 19 1 2 3 3 3 3 3 3 3 3 3 2 13 2 2 1 17 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1
output:
Alice
result:
ok "Alice"
Test #42:
score: 20
Accepted
time: 15ms
memory: 18244kb
input:
1 20 1 2 3 2 1 6 6 6 4 7 4 2 9 13 2 11 5 14 4 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 1 1 1 1 0
output:
Bob
result:
ok "Bob"
Test #43:
score: 20
Accepted
time: 19ms
memory: 20232kb
input:
1 19 1 1 3 3 3 4 1 5 5 2 5 11 4 4 4 6 17 17 1 0 1 0 0 1 0 0 1 1 0 1 1 0 0 1 0 0 1
output:
Bob
result:
ok "Bob"
Test #44:
score: 20
Accepted
time: 68ms
memory: 21076kb
input:
1 20 1 2 3 4 5 5 5 4 3 3 3 2 13 13 2 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 1 0 1 0 1
output:
Alice
result:
ok "Alice"
Test #45:
score: 20
Accepted
time: 11ms
memory: 19424kb
input:
1 19 1 1 2 1 5 1 6 5 7 5 1 8 9 4 4 8 7 17 0 1 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 1
output:
Bob
result:
ok "Bob"
Test #46:
score: 20
Accepted
time: 13ms
memory: 20080kb
input:
1 20 1 2 1 2 4 2 7 4 5 6 8 6 5 3 2 1 13 10 8 0 0 0 1 0 1 1 1 1 1 1 0 1 1 0 0 1 0 1 0
output:
Alice
result:
ok "Alice"
Test #47:
score: 20
Accepted
time: 20ms
memory: 20056kb
input:
1 19 1 2 2 4 4 4 3 3 6 4 4 4 10 3 6 7 17 4 0 0 1 1 0 0 1 0 1 0 0 0 1 0 1 1 0 1 0
output:
Alice
result:
ok "Alice"
Test #48:
score: 20
Accepted
time: 114ms
memory: 25088kb
input:
1 20 1 2 3 4 4 4 4 3 9 9 9 3 3 3 3 1 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0
output:
Bob
result:
ok "Bob"
Test #49:
score: 20
Accepted
time: 74ms
memory: 21728kb
input:
1 19 1 2 3 4 5 4 4 4 3 3 3 3 2 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 1
output:
Alice
result:
ok "Alice"
Subtask #2:
score: 0
Wrong Answer
Test #50:
score: 0
Wrong Answer
time: 9ms
memory: 18112kb
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:
result:
wrong answer Unexpected EOF in the participants output
Subtask #3:
score: 0
Wrong Answer
Test #73:
score: 0
Wrong Answer
time: 10ms
memory: 19420kb
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:
result:
wrong answer Unexpected EOF in the participants output
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%