QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#182710 | #4896. Alice、Bob 与 DFS | zhoukangyang | 0 | 3ms | 30144kb | C++11 | 1.3kb | 2023-09-18 14:22:33 | 2023-09-18 14:22:34 |
Judging History
answer
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector < int >
#define sz(a) ((int) (a).size())
#define ll long long
#define ull unsigned long long
#define me(a, x) memset(a, x, sizeof(a))
using namespace std;
const int N = 1e6 + 7;
int n;
int c[N];
vi e[N];
int dp[N];
int main() {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
L(i, 1, n) {
cin >> c[i];
}
L(i, 1, n) {
int m;
cin >> m;
while(m--) {
int x;
cin >> x;
e[i].emplace_back(x);
}
}
R(i, n, 1) {
if(c[i] == 0) {
R(j, sz(e[i]) - 1, 0) {
dp[i] ^= dp[e[i][j]];
}
dp[i] &= 1;
} else {
vi vc;
R(j, sz(e[i]) - 1, 0) {
int w = dp[e[i][j]];
int l = 0, r = sz(vc) - 1, ans = sz(vc);
while(l <= r) {
int mid = (l + r) >> 1;
if(w < vc[mid] - mid) ans = mid, r = mid - 1;
else l = mid + 1;
}
w += ans;
vc.insert(lower_bound(vc.begin(), vc.end(), w), w);
}
dp[i] = 0;
while(dp[i] < sz(vc) && vc[dp[i]] == dp[i]) ++dp[i];
}
}
int k;
cin >> k;
int ans = 0;
while(k--) {
int x;
cin >> x;
ans ^= dp[x];
}
if(ans == 0) cout << "Bob\n";
else cout << "Alice\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 30144kb
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:
wrong answer 1st words differ - expected: 'Alice', found: 'Bob'
Subtask #2:
score: 0
Wrong Answer
Test #18:
score: 15
Accepted
time: 3ms
memory: 28016kb
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:
Bob
result:
ok "Bob"
Test #19:
score: -15
Wrong Answer
time: 0ms
memory: 30132kb
input:
6 0 1 0 0 1 0 2 2 6 3 3 4 5 0 0 0 0 1 1
output:
Alice
result:
wrong answer 1st words differ - expected: 'Bob', found: 'Alice'
Subtask #3:
score: 0
Wrong Answer
Test #55:
score: 15
Accepted
time: 0ms
memory: 28084kb
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:
Bob
result:
ok "Bob"
Test #56:
score: -15
Wrong Answer
time: 0ms
memory: 28092kb
input:
6 0 1 0 0 1 0 2 2 6 3 3 4 5 0 0 0 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: 0ms
memory: 30072kb
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:
0%