QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#407914 | #4896. Alice、Bob 与 DFS | chenxinyang2006 | 0 | 2ms | 5416kb | C++20 | 2.4kb | 2024-05-09 14:40:43 | 2024-05-09 14:40:45 |
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%