75872024-01-09 21:15:22anonLámpákcpp17Időlimit túllépés 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1824 KiB
2Elfogadva3ms2024 KiB
subtask20/15
3Időlimit túllépés1.1s1572 KiB
4Időlimit túllépés1.085s2956 KiB
5Időlimit túllépés1.042s13796 KiB
subtask310/10
6Elfogadva303ms3476 KiB
7Elfogadva324ms3840 KiB
8Elfogadva589ms3812 KiB
9Elfogadva477ms4060 KiB
10Elfogadva418ms4180 KiB
subtask40/30
11Időlimit túllépés1.077s3636 KiB
12Időlimit túllépés1.05s4652 KiB
13Időlimit túllépés1.057s4760 KiB
14Időlimit túllépés1.067s4384 KiB
15Időlimit túllépés1.07s4428 KiB
16Időlimit túllépés1.074s5044 KiB
17Időlimit túllépés1.07s4324 KiB
subtask50/45
18Időlimit túllépés1.07s7152 KiB
19Időlimit túllépés1.062s8940 KiB
20Időlimit túllépés1.065s9360 KiB
21Időlimit túllépés1.07s12468 KiB
22Időlimit túllépés1.047s12688 KiB
23Időlimit túllépés1.075s16428 KiB
24Időlimit túllépés1.067s22028 KiB
25Időlimit túllépés1.039s23172 KiB
26Időlimit túllépés1.052s35188 KiB
27Időlimit túllépés1.062s36284 KiB
28Időlimit túllépés1.075s12580 KiB
29Időlimit túllépés1.059s12672 KiB