QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#188613 | #4589. White-Black Tree | 8BQube | WA | 2ms | 6408kb | C++17 | 1.3kb | 2023-09-26 04:36:27 | 2023-09-26 04:36:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back
const int C = 20;
vector<int> G[100005];
int clr[100005];
int sg(int u, int c) {
int res = 0;
if (c == 1) {
if (clr[u] == 0)
for (int i : G[u])
res ^= sg(i, c);
else
c = 0;
}
if (c == 0) {
int cnt[C] = {};
for (int i : G[u]) {
int val = sg(i, c);
for (int j = 0; j < C; ++j)
if (val >> j & 1)
++cnt[j];
}
for (int i = C - 1; i >= 0; --i) {
if (cnt[i] == 1) res |= 1 << i;
else if (cnt[i] > 1) {
res |= (1 << (i + 1)) - 1;
break;
}
}
++res;
}
return res;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
for (int i = 2; i <= n; ++i) {
int p;
cin >> p;
G[p].pb(i);
}
for (int i = 1; i <= n; ++i)
cin >> clr[i];
int res = sg(1, 1);
if (res) cout << "First\n";
else cout << "Second\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6188kb
input:
7 1 1 1 3 3 3 0 1 1 0 0 0 1
output:
First
result:
ok single line: 'First'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5996kb
input:
5 1 1 2 3 0 1 1 0 0
output:
Second
result:
ok single line: 'Second'
Test #3:
score: 0
Accepted
time: 1ms
memory: 6076kb
input:
4 1 1 1 1 1 0 1
output:
First
result:
ok single line: 'First'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5932kb
input:
2 1 0 0
output:
Second
result:
ok single line: 'Second'
Test #5:
score: 0
Accepted
time: 1ms
memory: 5932kb
input:
3 1 2 0 1 1
output:
First
result:
ok single line: 'First'
Test #6:
score: 0
Accepted
time: 0ms
memory: 5992kb
input:
3 1 2 1 1 1
output:
First
result:
ok single line: 'First'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5992kb
input:
3 1 1 1 1 1
output:
First
result:
ok single line: 'First'
Test #8:
score: 0
Accepted
time: 1ms
memory: 5988kb
input:
3 1 1 0 1 0
output:
First
result:
ok single line: 'First'
Test #9:
score: 0
Accepted
time: 1ms
memory: 5948kb
input:
3 1 1 0 1 1
output:
Second
result:
ok single line: 'Second'
Test #10:
score: 0
Accepted
time: 0ms
memory: 6052kb
input:
4 1 1 2 0 1 1 0
output:
First
result:
ok single line: 'First'
Test #11:
score: 0
Accepted
time: 1ms
memory: 5940kb
input:
4 1 1 1 0 1 1 1
output:
First
result:
ok single line: 'First'
Test #12:
score: 0
Accepted
time: 1ms
memory: 5996kb
input:
4 1 2 3 0 1 0 1
output:
First
result:
ok single line: 'First'
Test #13:
score: 0
Accepted
time: 1ms
memory: 5980kb
input:
5 1 1 2 2 0 1 1 1 1
output:
First
result:
ok single line: 'First'
Test #14:
score: 0
Accepted
time: 1ms
memory: 5932kb
input:
5 1 1 2 2 0 0 1 0 1
output:
Second
result:
ok single line: 'Second'
Test #15:
score: 0
Accepted
time: 1ms
memory: 6052kb
input:
2 1 1 0
output:
First
result:
ok single line: 'First'
Test #16:
score: 0
Accepted
time: 1ms
memory: 5980kb
input:
5 1 1 2 2 0 1 1 0 0
output:
First
result:
ok single line: 'First'
Test #17:
score: 0
Accepted
time: 1ms
memory: 6064kb
input:
5 1 1 1 2 0 1 1 1 1
output:
First
result:
ok single line: 'First'
Test #18:
score: 0
Accepted
time: 2ms
memory: 5948kb
input:
5 1 1 1 2 0 1 1 1 1
output:
First
result:
ok single line: 'First'
Test #19:
score: 0
Accepted
time: 1ms
memory: 6408kb
input:
5 1 1 2 3 0 1 1 1 1
output:
Second
result:
ok single line: 'Second'
Test #20:
score: -100
Wrong Answer
time: 1ms
memory: 5928kb
input:
5 1 1 2 3 0 1 1 1 0
output:
Second
result:
wrong answer 1st lines differ - expected: 'First', found: 'Second'