75922024-01-09 22:30:41anonLámpákcpp17Időlimit túllépés 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1888 KiB
2Elfogadva3ms2084 KiB
subtask20/15
3Időlimit túllépés1.1s2296 KiB
4Időlimit túllépés1.039s2752 KiB
5Időlimit túllépés1.059s11260 KiB
subtask310/10
6Elfogadva405ms2732 KiB
7Elfogadva441ms2820 KiB
8Elfogadva898ms2820 KiB
9Elfogadva727ms2964 KiB
10Elfogadva559ms2832 KiB
subtask40/30
11Időlimit túllépés1.07s2332 KiB
12Időlimit túllépés1.049s3136 KiB
13Időlimit túllépés1.062s3256 KiB
14Időlimit túllépés1.074s3424 KiB
15Időlimit túllépés1.047s2776 KiB
16Időlimit túllépés1.062s3620 KiB
17Időlimit túllépés1.077s3024 KiB
subtask50/45
18Időlimit túllépés1.065s5064 KiB
19Időlimit túllépés1.062s6280 KiB
20Időlimit túllépés1.062s6468 KiB
21Időlimit túllépés1.067s9628 KiB
22Időlimit túllépés1.078s9572 KiB
23Időlimit túllépés1.059s11236 KiB
24Időlimit túllépés1.059s16020 KiB
25Időlimit túllépés1.075s15904 KiB
26Időlimit túllépés1.075s29516 KiB
27Időlimit túllépés1.031s29596 KiB
28Időlimit túllépés1.07s4528 KiB
29Időlimit túllépés1.057s4640 KiB