QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#300758 | #4896. Alice、Bob 与 DFS | zyc070419 | 0 | 0ms | 0kb | C++14 | 4.2kb | 2024-01-08 19:04:15 | 2024-01-08 19:04:15 |
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< pair<int, int> > now;
vector<int> to[2000], tmp;
vector< vector< pair<int, 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, int lst) {
now.push_back(make_pair(x, lst));
tot.push_back(now);
for (int i = 0; i < g[x].size(); ++i) dfs(g[x][i], i);
now.pop_back();
}
void solve() {
for (int x = 1; x <= n; ++x) {
tot.clear(); dfs(x, 0); 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()) continue;
for (int j = i + 1; j < tot.size(); ++j) {
if (tot[j].size() <= tot[i].size()) {
if (tot[j].empty()) {
to[i].push_back(j);
continue;
}
bool pd = true;
for (int ID = 0; ID + 1 < tot[j].size(); ++ID)
if (tot[j][ID] != tot[i][ID]) pd = false;
if (!pd) continue;
to[i].push_back(j);
if (c[tot[j][tot[j].size() - 2].first] == 0) break;
}
if (tot[j].size() == tot[i].size() + 1 && tot[j][tot[i].size() - 1] == tot[i].back()) {
to[i].push_back(j);
if (c[tot[i].back().first] == 0) break;
}
}
}
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("sg[%d] = %d\n", i, sg[i]);
}
val[x] = sg[0];
}
int fin = 0;
for (auto x : vec) fin ^= val[x];
puts(fin ? "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);
// subtask3 :: solve(); exit(0);
if (subtask1 :: check()) subtask1 :: solve();
else if (subtask3 :: check()) subtask3 :: solve();
else if (subtask2 :: check()) subtask2 :: solve();
return 0;
}
详细
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%