75922024-01-09 22:30:41anonLámpákcpp17Time limit exceeded 10/1001.1s29596 KiB
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ost;
ost dfs(ll vertex, vector<bool> &states, const vector<vector<ll>> &tree) {
    bool si;
    ost signals;
    for(const auto &x : tree[vertex]) {
        auto ns = dfs(x, states, tree);
        for(const auto &y : ns)
            signals.insert(y);
    }
    si = (states[vertex] + signals.order_of_key(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;
        tree[u - 1].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, states, tree);
        cout << states[0] << '\n';
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1888 KiB
2Accepted3ms2084 KiB
subtask20/15
3Time limit exceeded1.1s2296 KiB
4Time limit exceeded1.039s2752 KiB
5Time limit exceeded1.059s11260 KiB
subtask310/10
6Accepted405ms2732 KiB
7Accepted441ms2820 KiB
8Accepted898ms2820 KiB
9Accepted727ms2964 KiB
10Accepted559ms2832 KiB
subtask40/30
11Time limit exceeded1.07s2332 KiB
12Time limit exceeded1.049s3136 KiB
13Time limit exceeded1.062s3256 KiB
14Time limit exceeded1.074s3424 KiB
15Time limit exceeded1.047s2776 KiB
16Time limit exceeded1.062s3620 KiB
17Time limit exceeded1.077s3024 KiB
subtask50/45
18Time limit exceeded1.065s5064 KiB
19Time limit exceeded1.062s6280 KiB
20Time limit exceeded1.062s6468 KiB
21Time limit exceeded1.067s9628 KiB
22Time limit exceeded1.078s9572 KiB
23Time limit exceeded1.059s11236 KiB
24Time limit exceeded1.059s16020 KiB
25Time limit exceeded1.075s15904 KiB
26Time limit exceeded1.075s29516 KiB
27Time limit exceeded1.031s29596 KiB
28Time limit exceeded1.07s4528 KiB
29Time limit exceeded1.057s4640 KiB