7592 2024. 01. 09 22:30:41 anon Lámpák cpp17 Időlimit túllépés 10/100 1.1s 29596 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1888 KiB
2 Elfogadva 3ms 2084 KiB
subtask2 0/15
3 Időlimit túllépés 1.1s 2296 KiB
4 Időlimit túllépés 1.039s 2752 KiB
5 Időlimit túllépés 1.059s 11260 KiB
subtask3 10/10
6 Elfogadva 405ms 2732 KiB
7 Elfogadva 441ms 2820 KiB
8 Elfogadva 898ms 2820 KiB
9 Elfogadva 727ms 2964 KiB
10 Elfogadva 559ms 2832 KiB
subtask4 0/30
11 Időlimit túllépés 1.07s 2332 KiB
12 Időlimit túllépés 1.049s 3136 KiB
13 Időlimit túllépés 1.062s 3256 KiB
14 Időlimit túllépés 1.074s 3424 KiB
15 Időlimit túllépés 1.047s 2776 KiB
16 Időlimit túllépés 1.062s 3620 KiB
17 Időlimit túllépés 1.077s 3024 KiB
subtask5 0/45
18 Időlimit túllépés 1.065s 5064 KiB
19 Időlimit túllépés 1.062s 6280 KiB
20 Időlimit túllépés 1.062s 6468 KiB
21 Időlimit túllépés 1.067s 9628 KiB
22 Időlimit túllépés 1.078s 9572 KiB
23 Időlimit túllépés 1.059s 11236 KiB
24 Időlimit túllépés 1.059s 16020 KiB
25 Időlimit túllépés 1.075s 15904 KiB
26 Időlimit túllépés 1.075s 29516 KiB
27 Időlimit túllépés 1.031s 29596 KiB
28 Időlimit túllépés 1.07s 4528 KiB
29 Időlimit túllépés 1.057s 4640 KiB