oj.uz

Submission #814842

# Submission time Handle Problem Language Result Execution time Memory
814842 2023-08-08T10:29:43 Z finn__ Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 162 ms 16220 KB 
#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];
            if (h.g[a[i]].size() > 1 || no_leaf_anymore[a[i]])
                num_leafs++;
            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;

        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)
        {
            if (h.g[a[i]].size() > 1 || no_leaf_anymore[a[i]])
                num_leafs--;
            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;
    }
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 92 ms 6324 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 5824 KB Output is correct
2 Correct 11 ms 5716 KB Output is correct
3 Correct 26 ms 11704 KB Output is correct
4 Correct 48 ms 10276 KB Output is correct
5 Correct 70 ms 12272 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 6100 KB Output is correct
2 Correct 9 ms 6100 KB Output is correct
3 Correct 50 ms 14840 KB Output is correct
4 Correct 104 ms 14740 KB Output is correct
5 Correct 30 ms 13912 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 6796 KB Output is correct
2 Correct 32 ms 6740 KB Output is correct
3 Correct 9 ms 6404 KB Output is correct
4 Correct 11 ms 6724 KB Output is correct
5 Correct 12 ms 6968 KB Output is correct
6 Correct 40 ms 6928 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 9892 KB Output is correct
2 Correct 147 ms 9676 KB Output is correct
3 Correct 114 ms 8288 KB Output is correct
4 Correct 135 ms 10928 KB Output is correct
5 Correct 138 ms 10924 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 11892 KB Output is correct
2 Correct 64 ms 13912 KB Output is correct
3 Correct 145 ms 12816 KB Output is correct
4 Correct 56 ms 13304 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 92 ms 6324 KB Output is correct
3 Correct 43 ms 5824 KB Output is correct
4 Correct 11 ms 5716 KB Output is correct
5 Correct 26 ms 11704 KB Output is correct
6 Correct 48 ms 10276 KB Output is correct
7 Correct 70 ms 12272 KB Output is correct
8 Correct 43 ms 6100 KB Output is correct
9 Correct 9 ms 6100 KB Output is correct
10 Correct 50 ms 14840 KB Output is correct
11 Correct 104 ms 14740 KB Output is correct
12 Correct 30 ms 13912 KB Output is correct
13 Correct 68 ms 6796 KB Output is correct
14 Correct 32 ms 6740 KB Output is correct
15 Correct 9 ms 6404 KB Output is correct
16 Correct 11 ms 6724 KB Output is correct
17 Correct 12 ms 6968 KB Output is correct
18 Correct 40 ms 6928 KB Output is correct
19 Correct 47 ms 9892 KB Output is correct
20 Correct 147 ms 9676 KB Output is correct
21 Correct 114 ms 8288 KB Output is correct
22 Correct 135 ms 10928 KB Output is correct
23 Correct 138 ms 10924 KB Output is correct
24 Correct 162 ms 11892 KB Output is correct
25 Correct 64 ms 13912 KB Output is correct
26 Correct 145 ms 12816 KB Output is correct
27 Correct 56 ms 13304 KB Output is correct
28 Correct 118 ms 10196 KB Output is correct
29 Correct 103 ms 15144 KB Output is correct
30 Correct 39 ms 13596 KB Output is correct
31 Correct 80 ms 16220 KB Output is correct
32 Correct 151 ms 11008 KB Output is correct
33 Correct 153 ms 12812 KB Output is correct
34 Correct 158 ms 14552 KB Output is correct
35 Correct 132 ms 14512 KB Output is correct