75872024-01-09 21:15:22anonLámpákcpp17Time limit exceeded 10/1001.1s36284 KiB
#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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1824 KiB
2Accepted3ms2024 KiB
subtask20/15
3Time limit exceeded1.1s1572 KiB
4Time limit exceeded1.085s2956 KiB
5Time limit exceeded1.042s13796 KiB
subtask310/10
6Accepted303ms3476 KiB
7Accepted324ms3840 KiB
8Accepted589ms3812 KiB
9Accepted477ms4060 KiB
10Accepted418ms4180 KiB
subtask40/30
11Time limit exceeded1.077s3636 KiB
12Time limit exceeded1.05s4652 KiB
13Time limit exceeded1.057s4760 KiB
14Time limit exceeded1.067s4384 KiB
15Time limit exceeded1.07s4428 KiB
16Time limit exceeded1.074s5044 KiB
17Time limit exceeded1.07s4324 KiB
subtask50/45
18Time limit exceeded1.07s7152 KiB
19Time limit exceeded1.062s8940 KiB
20Time limit exceeded1.065s9360 KiB
21Time limit exceeded1.07s12468 KiB
22Time limit exceeded1.047s12688 KiB
23Time limit exceeded1.075s16428 KiB
24Time limit exceeded1.067s22028 KiB
25Time limit exceeded1.039s23172 KiB
26Time limit exceeded1.052s35188 KiB
27Time limit exceeded1.062s36284 KiB
28Time limit exceeded1.075s12580 KiB
29Time limit exceeded1.059s12672 KiB