QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#300739 | #4896. Alice、Bob 与 DFS | zyc070419 | 5 | 25ms | 16852kb | C++14 | 3.5kb | 2024-01-08 18:20:12 | 2024-01-08 18:20:12 |
Judging History
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];
bool check() {return vec.size() == 1;}
void solve() {
for (int x = n; x >= 1; --x) {
if (g[x].empty()) dp[x] = 1;
else {
if (c[x] == 0) {
int val = 1;
for (auto y : g[x]) {
if (dp[y] <= 1) val ^= dp[y];
else {
val ^= dp[y];
break;
}
}
dp[x] = val;
}else {
}
}
}
puts((dp[vec[0]] == 1 || dp[vec[0]] == 2) ? "Alice" : "Bob");
}
}
namespace subtask3 {
int cnt, val[N], sg[2000];
vector<int> now, to[2000], tmp;
vector< vector<int> > tot;
bool check() {
int m = 0;
for (int x = 1; x <= n; ++x) m += g[x].size();
return (n <= 10 && m <= 10);
}
void dfs(int x) {
now.push_back(x);
tot.push_back(now);
for (auto y : g[x]) dfs(y);
now.pop_back();
}
void solve() {
for (int x = 1; x <= n; ++x) {
tot.clear(); dfs(x); tot.push_back(now);
for (int i = 0; i < tot.size(); ++i) to[i].clear();
for (int i = 0; i < tot.size(); ++i) {
if (tot[i].empty() || c[tot[i].back()] == 0) continue;
for (int j = i + 1; j < tot.size(); ++j) {
if (tot[j].size() <= tot[i].size()) to[i].push_back(j);
if (tot[j].size() == tot[i].size() + 1 && tot[j][tot[i].size() - 1] == tot[i].back())
to[i].push_back(j);
}
}
for (int i = tot.size() - 1; i >= 0; --i) {
tmp.clear();
for (auto j : to[i]) tmp.push_back(sg[j]);
sort(tmp.begin(), tmp.end());
int ans = 0;
while (ans < tmp.size() && ans == tmp[ans]) ans++;
sg[i] = ans;
// if (x == 1) printf("[%d]\n", sg[i]);
}
val[x] = sg[0];
}
int fin = 0;
for (auto x : vec) fin ^= val[x];
puts(fin ? "Alice" : "Bob");
}
}
int main() {
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);
// subtask3 :: solve(); exit(0);
if (subtask1 :: check()) subtask1 :: solve();
else if (subtask2 :: check()) subtask2 :: solve();
else if (subtask3 :: check()) subtask3 :: solve();
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 2ms
memory: 8392kb
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:
Alice
result:
ok "Alice"
Test #2:
score: 0
Accepted
time: 0ms
memory: 9552kb
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:
Bob
result:
ok "Bob"
Test #3:
score: 0
Accepted
time: 0ms
memory: 9708kb
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:
Alice
result:
ok "Alice"
Test #4:
score: 0
Accepted
time: 2ms
memory: 8716kb
input:
10 0 0 0 0 0 0 0 0 0 0 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 0 1 1
output:
Bob
result:
ok "Bob"
Test #5:
score: 0
Accepted
time: 0ms
memory: 8336kb
input:
11 0 0 0 0 0 0 0 0 0 0 0 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 0 0 2 1 11
output:
Alice
result:
ok "Alice"
Test #6:
score: 0
Accepted
time: 3ms
memory: 16844kb
input:
200000 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:
Bob
result:
ok "Bob"
Test #7:
score: 0
Accepted
time: 11ms
memory: 16852kb
input:
200000 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:
Bob
result:
ok "Bob"
Test #8:
score: 0
Accepted
time: 24ms
memory: 15392kb
input:
200000 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:
Alice
result:
ok "Alice"
Test #9:
score: 0
Accepted
time: 25ms
memory: 15604kb
input:
200000 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:
Bob
result:
ok "Bob"
Test #10:
score: 0
Accepted
time: 14ms
memory: 16060kb
input:
200000 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:
Bob
result:
ok "Bob"
Test #11:
score: 0
Accepted
time: 22ms
memory: 13344kb
input:
200000 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:
Bob
result:
ok "Bob"
Test #12:
score: 0
Accepted
time: 19ms
memory: 14240kb
input:
200000 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:
Bob
result:
ok "Bob"
Test #13:
score: 0
Accepted
time: 18ms
memory: 13784kb
input:
200000 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:
Alice
result:
ok "Alice"
Test #14:
score: 0
Accepted
time: 15ms
memory: 13864kb
input:
200000 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:
Bob
result:
ok "Bob"
Test #15:
score: 0
Accepted
time: 2ms
memory: 9800kb
input:
1 0 0 1 1
output:
Alice
result:
ok "Alice"
Test #16:
score: 0
Accepted
time: 2ms
memory: 9616kb
input:
3 0 0 0 1 2 1 3 0 1 1
output:
Alice
result:
ok "Alice"
Test #17:
score: 0
Accepted
time: 2ms
memory: 9520kb
input:
4 0 0 0 0 1 2 1 3 0 0 2 1 4
output:
Bob
result:
ok "Bob"
Subtask #2:
score: 0
Wrong Answer
Test #18:
score: 0
Wrong Answer
time: 0ms
memory: 8840kb
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:
Alice
result:
wrong answer 1st words differ - expected: 'Bob', found: 'Alice'
Subtask #3:
score: 0
Wrong Answer
Test #55:
score: 0
Wrong Answer
time: 2ms
memory: 9956kb
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:
Alice
result:
wrong answer 1st words differ - expected: 'Bob', found: 'Alice'
Subtask #4:
score: 0
Wrong Answer
Test #103:
score: 0
Wrong Answer
time: 2ms
memory: 8724kb
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:
Bob
result:
wrong answer 1st words differ - expected: 'Alice', found: 'Bob'
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%