7587 2024. 01. 09 21:15:22 anon Lámpák cpp17 Időlimit túllépés 10/100 1.1s 36284 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1824 KiB
2 Elfogadva 3ms 2024 KiB
subtask2 0/15
3 Időlimit túllépés 1.1s 1572 KiB
4 Időlimit túllépés 1.085s 2956 KiB
5 Időlimit túllépés 1.042s 13796 KiB
subtask3 10/10
6 Elfogadva 303ms 3476 KiB
7 Elfogadva 324ms 3840 KiB
8 Elfogadva 589ms 3812 KiB
9 Elfogadva 477ms 4060 KiB
10 Elfogadva 418ms 4180 KiB
subtask4 0/30
11 Időlimit túllépés 1.077s 3636 KiB
12 Időlimit túllépés 1.05s 4652 KiB
13 Időlimit túllépés 1.057s 4760 KiB
14 Időlimit túllépés 1.067s 4384 KiB
15 Időlimit túllépés 1.07s 4428 KiB
16 Időlimit túllépés 1.074s 5044 KiB
17 Időlimit túllépés 1.07s 4324 KiB
subtask5 0/45
18 Időlimit túllépés 1.07s 7152 KiB
19 Időlimit túllépés 1.062s 8940 KiB
20 Időlimit túllépés 1.065s 9360 KiB
21 Időlimit túllépés 1.07s 12468 KiB
22 Időlimit túllépés 1.047s 12688 KiB
23 Időlimit túllépés 1.075s 16428 KiB
24 Időlimit túllépés 1.067s 22028 KiB
25 Időlimit túllépés 1.039s 23172 KiB
26 Időlimit túllépés 1.052s 35188 KiB
27 Időlimit túllépés 1.062s 36284 KiB
28 Időlimit túllépés 1.075s 12580 KiB
29 Időlimit túllépés 1.059s 12672 KiB