Submission #814831

#	Time	Username	Problem	Language	Result	Execution time	Memory
814831		finn__	Spring cleaning (CEOI20_cleaning)	C++17	26 / 100	148 ms	14944 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;

template <size_t L>
struct Segtree
{
    int t[L << 1];
    bitset<L << 1> lzy;

    void set(size_t i, int x) { t[i + L] = x; }

    void build()
    {
        for (size_t i = L - 1; i; --i)
            t[i] = t[i << 1] + t[i << 1 | 1];
    }

    void propagate(size_t k, size_t a, size_t b)
    {
        if (lzy[k])
        {
            lzy[k << 1] = !lzy[k << 1];
            lzy[k << 1 | 1] = !lzy[k << 1 | 1];
            t[k << 1] = (b - a + 1) / 2 - t[k << 1];
            t[k << 1 | 1] = (b - a + 1) / 2 - t[k << 1 | 1];
            lzy[k] = 0;
        }
    }

    void flip(size_t i, size_t j, size_t k = 1, size_t a = 0, size_t b = L - 1)
    {
        if (b < i || a > j)
            return;
        if (i <= a && b <= j)
        {
            lzy[k] = !lzy[k];
            t[k] = b - a + 1 - t[k];
        }
        else
        {
            propagate(k, a, b);
            flip(i, j, k << 1, a, (a + b) >> 1);
            flip(i, j, k << 1 | 1, ((a + b) >> 1) + 1, b);
            t[k] = t[k << 1] + t[k << 1 | 1];
        }
    }

    int sum(size_t i, size_t j, size_t k = 1, size_t a = 0, size_t b = L - 1)
    {
        if (b < i || a > j)
            return 0;
        if (i <= a && b <= j)
            return t[k];
        propagate(k, a, b);
        return sum(i, j, k << 1, a, (a + b) >> 1) + sum(i, j, k << 1 | 1, ((a + b) >> 1) + 1, b);
    }
};

template <size_t N>
struct Hld
{
    vector<size_t> g[N];
    size_t root[N], parent[N], subtree_size[N], ind[N];
    Segtree<N> tree;

    void add_edge(size_t u, size_t v)
    {
        g[u].push_back(v);
        g[v].push_back(u);
    }

    void build()
    {
        memset(parent, 255, sizeof parent);
        find_heavy(0);
        find_root(0);
        init_segtree(0);
        tree.build();
    }

    void find_heavy(size_t u)
    {
        subtree_size[u] = 1;
        for (auto &v : g[u])
            if (v != parent[u])
            {
                parent[v] = u;
                find_heavy(v);
                subtree_size[u] += subtree_size[v];

                if (g[u][0] == parent[u] || subtree_size[v] > subtree_size[g[u][0]])
                    swap(v, g[u][0]);
            }
    }

    size_t find_root(size_t u, size_t i = 0)
    {
        ind[u] = i++;
        for (auto const &v : g[u])
            if (v != parent[u])
            {
                root[v] = v == g[u][0] ? root[u] : v;
                i = find_root(v, i);
            }
        return i;
    }

    bool init_segtree(size_t u)
    {
        bool leaf_parity = g[u].size() == 1;
        for (auto const &v : g[u])
            if (v != parent[u])
                leaf_parity ^= init_segtree(v);
        tree.set(ind[u], leaf_parity);
        return leaf_parity;
    }

    void update_root_path(size_t u)
    {
        while (u != SIZE_MAX)
        {
            tree.flip(ind[root[u]], ind[u]);
            u = parent[root[u]];
        }
    }
};

constexpr size_t N = 1 << 17;

Hld<N> h;
size_t a[N];
bitset<N> no_leaf_anymore;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, q;
    cin >> n >> q;
    for (size_t i = 0; i < n - 1; ++i)
    {
        size_t u, v;
        cin >> u >> v;
        h.add_edge(u - 1, v - 1);
    }

    h.build();

    size_t num_leafs = 0;
    for (size_t i = 0; i < n; ++i)
        num_leafs += h.g[i].size() == 1;

    while (q--)
    {
        size_t d;
        cin >> d;
        for (size_t i = 0; i < d; ++i)
        {
            cin >> a[i], --a[i];
            num_leafs += h.g[a[i]].size() > 1;
        }

        if (!(num_leafs & 1))
        {
            for (size_t i = 0; i < d; ++i)
                if (h.g[a[i]].size() > 1 || no_leaf_anymore[a[i]])
                    h.update_root_path(a[i]);
                else if (h.g[a[i]].size() == 1)
                    no_leaf_anymore[a[i]] = 1;
            for (size_t i = 0; i < d; ++i)
                no_leaf_anymore[a[i]] = 0;

            cout << 2 * (n - 1) + d - h.tree.sum(0, n - 1) << '\n';

            for (size_t i = 0; i < d; ++i)
                if (h.g[a[i]].size() > 1 || no_leaf_anymore[a[i]])
                    h.update_root_path(a[i]);
                else if (h.g[a[i]].size() == 1)
                    no_leaf_anymore[a[i]] = 1;
            for (size_t i = 0; i < d; ++i)
                no_leaf_anymore[a[i]] = 0;
        }
        else
        {
            cout << "-1\n";
        }

        for (size_t i = 0; i < d; ++i)
            num_leafs -= h.g[a[i]].size() > 1;
    }
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 9
• Subtask 3: 9 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 17 / 17
• Subtask 7: 0 / 30