QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#300643 | #4896. Alice、Bob 与 DFS | zyc070419 | 0 | 0ms | 0kb | C++14 | 2.5kb | 2024-01-08 15:39:23 | 2024-01-08 15:39:23 |
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 3;
inline int read() {
char ch = getchar(); int x = 0;
while (!isdigit(ch)) {ch = getchar();}
while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
return x;
}
int n, c[N];
vector<int> g[N], vec;
namespace subtask1 {
bool dp[N], ans;
bool check() {
for (int i = 1; i <= n; ++i)
if (c[i] == 1) return false;
return true;
}
void solve() {
for (int x = n; x >= 1; --x) {
dp[x] = 1;
for (auto y : g[x]) dp[x] ^= dp[y];
}
for (auto r : vec) ans ^= dp[r];
puts(ans ? "Alice" : "Bob");
}
}
namespace subtask2 {
int dp[N];
//0: must fir
//1: must sec
//2: fir win
//3: sec win
bool check() {return vec.size() == 1;}
void solve() {
for (int x = n; x >= 1; --x) {
if (g[x].empty()) dp[x] = 1;
else {
int val = 1;
for (auto y : g[x]) {
if (val == 0) {
if (dp[y] == 0) val = 0;
else if (dp[y] == 1) val = 1;
else {
val = dp[y];
break;
}
}else {
if (dp[y] == 0) val = 1;
else if (dp[y] == 1) val = 0;
else {
val = dp[y] ^ 1;
break;
}
}
}
if (c[x] == 0) dp[x] = val;
else {
if (val == 3) dp[x] = 1;
else if (val == 0) dp[x] = 2;
else dp[x] = val;
}
}
// printf("dp[%d] = %d\n", x, dp[x]);
}
puts((dp[vec[0]] == 1 || dp[vec[0]] == 2) ? "Alice" : "Bob");
}
}
int main() {
freopen("in.in", "r", stdin);
freopen("mine.out", "w", stdout);
n = read();
for (int i = 1; i <= n; ++i) c[i] = read();
for (int x = 1, m, y; x <= n; ++x) {
m = read();
while (m--) {
y = read();
g[x].push_back(y);
}
}
int k = read(), x;
while (k--) x = read(), vec.push_back(x);
if (subtask1 :: check()) subtask1 :: solve();
else if (subtask2 :: check()) subtask2 :: solve();
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
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
Dangerous Syscalls
Test #18:
score: 0
Dangerous Syscalls
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
Dangerous Syscalls
Test #55:
score: 0
Dangerous Syscalls
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
Dangerous Syscalls
Test #103:
score: 0
Dangerous Syscalls
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:
result:
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%