171812025-05-29 12:06:04AblablablaGyors utakcpp17Futási hiba 0/1001ms576 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<vector<ll>> csucsok;
vector<ll> tin, tout;
ll ido;

void dfs(ll akt){
    tin[akt] = ido;
    ido++;

    for(ll x : csucsok[akt]){
        dfs(x);
    }

    tout[akt] = ido;
    ido++;
}

struct segTree{
    ll meret = 1;
    vector<ll> fa;
    vector<bool> csere;

    void meretez(ll n){
        while(meret < n){
            meret *= 2;
        }

        fa.assign(2*meret - 1, 0);
        csere.assign(2*meret - 1, 0);
    }

    ll keres(ll a, ll b, ll ind, ll kezd, ll veg){
        if(veg < kezd){
            return 0;
        }
        if(veg < a || b < kezd){
            return 0;
        } else if(kezd <= a && b <= veg){
            return fa[ind];
        }

        ll k = (a + b) / 2;

        ll akt = keres(a, k, 2*ind +1, kezd, veg) + keres(k + 1, b, 2*ind + 2, kezd, veg);

        if(csere[ind]){
            akt = (b - a + 1) - akt;
        }

        return akt;
    }

    ll valt(ll a, ll b, ll ind, ll kezd, ll veg){
        if(veg < a || b < kezd){
            return fa[ind];
        } else if(kezd <= a && b <= veg){
            fa[ind] = (b - a + 1) - fa[ind];
            csere[ind] = !csere[ind];
            return fa[ind];
        }

        ll k = (a + b) / 2;

        fa[ind] = valt(a, k, 2*ind + 1, kezd, veg) + valt(k + 1, b, 2*ind + 2, kezd, veg);

        if(csere[ind]){
            fa[ind] = (b - a + 1) - fa[ind];
        }

        return fa[ind];
    }
};

int main(){
    auto abc = ifstream("be2.txt");

    ll n, q;
    abc >> n >> q;

    csucsok.assign(n, vector<ll>());
    tin.assign(n, 0);
    tout.assign(n, 0);

    for(ll i = 1; i < n; i++){
        ll a;
        abc >> a;
        a--;

        csucsok[a].push_back(i);
    }
    cout << "beolvas kesz\n";

    dfs(0);
    cout << "dfs kesz\n";

    segTree fa;
    fa.meretez(2*n);

    for(ll i = 1; i < n; i++){
        ll a;
        abc >> a;

        if(a){
            fa.valt(0, fa.meret - 1, 0, tin[i], tout[i]);
        }

        cout << i << " kesz\n";
    }

    ll ps = fa.fa[0]/2;
    ll pt = n - ps;

    cout << (ps*(ps - 1) + pt*(pt - 1))/2 << " ";

    while(q--){
        ll a;
        abc >> a;

        fa.valt(0, fa.meret - 1, 0, tin[a], tout[a]);

        ps = fa.fa[0]/2;
        pt = n - ps;
        cout << (ps*(ps - 1) + pt*(pt - 1))/2 << " ";
    }
    cout << "\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Futási hiba1ms316 KiB
2Futási hiba1ms316 KiB
subtask20/10
3Futási hiba1ms576 KiB
4Futási hiba1ms316 KiB
5Futási hiba1ms316 KiB
6Futási hiba1ms316 KiB
7Futási hiba1ms500 KiB
8Futási hiba1ms316 KiB
subtask30/11
9Futási hiba1ms576 KiB
10Futási hiba1ms316 KiB
11Futási hiba1ms316 KiB
12Futási hiba1ms316 KiB
13Futási hiba1ms500 KiB
14Futási hiba1ms316 KiB
15Futási hiba1ms316 KiB
16Futási hiba1ms316 KiB
17Futási hiba1ms316 KiB
18Futási hiba1ms316 KiB
19Futási hiba1ms496 KiB
20Futási hiba1ms508 KiB
21Futási hiba1ms316 KiB
22Futási hiba1ms316 KiB
23Futási hiba1ms564 KiB
24Futási hiba1ms500 KiB
subtask40/21
25Futási hiba1ms316 KiB
26Futási hiba1ms316 KiB
27Futási hiba1ms332 KiB
28Futási hiba1ms316 KiB
29Futási hiba1ms512 KiB
30Futási hiba1ms496 KiB
subtask50/24
31Futási hiba1ms316 KiB
32Futási hiba1ms316 KiB
33Futási hiba1ms316 KiB
34Futási hiba1ms508 KiB
subtask60/34
35Futási hiba1ms576 KiB
36Futási hiba1ms316 KiB
37Futási hiba1ms316 KiB
38Futási hiba1ms316 KiB
39Futási hiba1ms500 KiB
40Futási hiba1ms316 KiB
41Futási hiba1ms316 KiB
42Futási hiba1ms316 KiB
43Futási hiba1ms316 KiB
44Futási hiba1ms316 KiB
45Futási hiba1ms496 KiB
46Futási hiba1ms508 KiB
47Futási hiba1ms316 KiB
48Futási hiba1ms316 KiB
49Futási hiba1ms564 KiB
50Futási hiba1ms500 KiB
51Futási hiba1ms316 KiB
52Futási hiba1ms316 KiB
53Futási hiba1ms332 KiB
54Futási hiba1ms316 KiB
55Futási hiba1ms512 KiB
56Futási hiba1ms496 KiB
57Futási hiba1ms316 KiB
58Futási hiba1ms316 KiB
59Futási hiba1ms316 KiB
60Futási hiba1ms508 KiB
61Futási hiba1ms316 KiB
62Futási hiba1ms316 KiB
63Futási hiba1ms508 KiB
64Futási hiba1ms316 KiB
65Futási hiba1ms512 KiB
66Futási hiba1ms512 KiB
67Futási hiba1ms316 KiB
68Futási hiba1ms316 KiB
69Futási hiba1ms316 KiB
70Futási hiba1ms316 KiB
71Futási hiba1ms316 KiB
72Futási hiba1ms316 KiB
73Futási hiba1ms512 KiB
74Futási hiba1ms316 KiB
75Futási hiba1ms316 KiB
76Futási hiba1ms316 KiB
77Futási hiba1ms508 KiB