#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define FastIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long long ll;
set<ll> dfs(ll vertex, ll parent, vector<bool> &states, const vector<vector<ll>> &tree) {
bool si;
set<ll> signals;
for(const auto &x : tree[vertex]) {
if(x == parent)
continue;
set<ll> ns = dfs(x, vertex, states, tree);
signals.insert(all(ns));
}
si = (states[vertex] + distance(signals.begin(), signals.lower_bound(vertex))) % 2;
states[vertex] = (states[vertex] + signals.size()) % 2;
if(si)
signals.insert(vertex);
return signals;
}
int main() {
FastIO;
ll i, u, s, N, K, Q;
cin >> N >> K >> Q;
vector<vector<ll>> tree(N);
for(i = 1; i < N; i++) {
cin >> u;
u--;
tree[i].push_back(u);
tree[u].push_back(i);
}
vector<bool> states(N);
while(Q--) {
for(i = 0; i < N; i++) {
cin >> s;
states[i] = s;
}
for(i = 0; i < K; i++)
dfs(0, -1, states, tree);
cout << states[0] << '\n';
}
return 0;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 1824 KiB | ||||
2 | Accepted | 3ms | 2024 KiB | ||||
subtask2 | 0/15 | ||||||
3 | Time limit exceeded | 1.1s | 1572 KiB | ||||
4 | Time limit exceeded | 1.085s | 2956 KiB | ||||
5 | Time limit exceeded | 1.042s | 13796 KiB | ||||
subtask3 | 10/10 | ||||||
6 | Accepted | 303ms | 3476 KiB | ||||
7 | Accepted | 324ms | 3840 KiB | ||||
8 | Accepted | 589ms | 3812 KiB | ||||
9 | Accepted | 477ms | 4060 KiB | ||||
10 | Accepted | 418ms | 4180 KiB | ||||
subtask4 | 0/30 | ||||||
11 | Time limit exceeded | 1.077s | 3636 KiB | ||||
12 | Time limit exceeded | 1.05s | 4652 KiB | ||||
13 | Time limit exceeded | 1.057s | 4760 KiB | ||||
14 | Time limit exceeded | 1.067s | 4384 KiB | ||||
15 | Time limit exceeded | 1.07s | 4428 KiB | ||||
16 | Time limit exceeded | 1.074s | 5044 KiB | ||||
17 | Time limit exceeded | 1.07s | 4324 KiB | ||||
subtask5 | 0/45 | ||||||
18 | Time limit exceeded | 1.07s | 7152 KiB | ||||
19 | Time limit exceeded | 1.062s | 8940 KiB | ||||
20 | Time limit exceeded | 1.065s | 9360 KiB | ||||
21 | Time limit exceeded | 1.07s | 12468 KiB | ||||
22 | Time limit exceeded | 1.047s | 12688 KiB | ||||
23 | Time limit exceeded | 1.075s | 16428 KiB | ||||
24 | Time limit exceeded | 1.067s | 22028 KiB | ||||
25 | Time limit exceeded | 1.039s | 23172 KiB | ||||
26 | Time limit exceeded | 1.052s | 35188 KiB | ||||
27 | Time limit exceeded | 1.062s | 36284 KiB | ||||
28 | Time limit exceeded | 1.075s | 12580 KiB | ||||
29 | Time limit exceeded | 1.059s | 12672 KiB |