Submission #896610

#	Time	Username	Problem	Language	Result	Execution time	Memory
896610		0x34c	Spring cleaning (CEOI20_cleaning)	C++17	26 / 100	189 ms	22352 KiB

cleaning

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'

using namespace std;

class SegmentTree
{
private:
    // first = even, second = odd
    vector<pii> tree;
    vector<int> lazy;
    int n;

    void build(vector<pii> &arr, int v, int tl, int tr)
    {
        if (tl == tr)
            tree[v] = arr[tl];
        else
        {
            int m = (tl + tr) / 2;
            build(arr, 2 * v, tl, m);
            build(arr, 2 * v + 1, m + 1, tr);
            tree[v].first = tree[2 * v].first + tree[2 * v + 1].first;
            tree[v].second = tree[2 * v].second + tree[2 * v + 1].second;
        }
    }

    pii _query(int l, int r, int v, int tl, int tr)
    {
        if (lazy[v] != 0)
        {
            if (lazy[v] & 1)
                swap(tree[v].first, tree[v].second);
            if (tl != tr)
            {
                lazy[2 * v] += lazy[v];
                lazy[2 * v + 1] += lazy[v];
            }
            lazy[v] = 0;
        }

        if (r < tl || tr < l)
            return {0, 0};

        if (l <= tl && tr <= r)
            return tree[v];

        int m = (tl + tr) / 2;
        pii lpi = _query(l, r, 2 * v, tl, m), rpi = _query(l, r, 2 * v + 1, m + 1, tr);
        return {lpi.first + rpi.first, lpi.second + rpi.second};
    }

    void _update(int l, int r, int v, int tl, int tr)
    {
        if (lazy[v] != 0)
        {
            if (lazy[v] & 1)
                swap(tree[v].first, tree[v].second);
            if (tl != tr)
            {
                lazy[2 * v] += lazy[v];
                lazy[2 * v + 1] += lazy[v];
            }
            lazy[v] = 0;
        }

        if (tr < l || r < tl)
            return;
        if (l <= tl && tr <= r)
        {
            swap(tree[v].first, tree[v].second);
            if (tl != tr)
            {
                lazy[2 * v]++;
                lazy[2 * v + 1]++;
            }
            return;
        }

        int m = (tl + tr) / 2;
        _update(l, r, 2 * v, tl, m);
        _update(l, r, 2 * v + 1, m + 1, tr);
        tree[v].first = tree[2 * v].first + tree[2 * v + 1].first;
        tree[v].second = tree[2 * v].second + tree[2 * v + 1].second;
    }

public:
    SegmentTree() {}
    void resize(vector<pii> &arr)
    {
        n = arr.size();
        tree.resize(4 * n);
        lazy.resize(4 * n, 0);
        build(arr, 1, 0, n - 1);
    }

    pii query(int l, int r)
    {
        if (l > r)
            swap(l, r);
        return _query(l, r, 1, 0, n - 1);
    }

    void update(int l, int r)
    {
        if (l > r)
            swap(l, r);
        return _update(l, r, 1, 0, n - 1);
    }
};

vector<vector<int>> graph;
vector<int> sz, leaf_cnt, label, depth, top, par;
SegmentTree tree;

int init_hld(int v, int p)
{
    sz[v] = 1;
    if (graph[v].size() == 1)
        leaf_cnt[v] = 1;

    for (int i = 0; i < graph[v].size(); i++)
    {
        int u = graph[v][i];
        if (u == p)
            continue;
        depth[u] = 1 + depth[v];
        par[u] = v;
        sz[v] += init_hld(u, v);
        leaf_cnt[v] += leaf_cnt[u];
        if (sz[u] > sz[graph[v][0]])
            swap(graph[v][0], graph[v][i]);
    }
    return sz[v];
}

void label_hld(int v, int p, int tp, int &id)
{
    label[v] = id++;
    top[v] = tp;

    for (int i = 0; i < graph[v].size(); i++)
    {
        int u = graph[v][i];
        if (u == p)
            continue;
        label_hld(u, v, (i == 0 ? tp : u), id);
    }
}

int hld_lca(int a, int b)
{
    while (top[a] != top[b])
    {
        if (depth[top[a]] > depth[top[b]])
            a = par[top[a]];
        else
            b = par[top[b]];
    }

    return depth[a] < depth[b] ? a : b;
}

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

    int n, q;
    cin >> n >> q;

    graph.resize(n);
    sz.resize(n);
    leaf_cnt.resize(n, 0);
    label.resize(n);
    depth.resize(n, 0);
    top.resize(n, 0);
    par.resize(n, 0);

    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;

        graph[--a].push_back(--b);
        graph[b].push_back(a);
    }

    init_hld(0, -1);
    int id = 0;
    label_hld(0, -1, 0, id);

    vector<pii> init_seg(id);
    for (int i = 0; i < n; i++)
        init_seg[label[i]] = {!(leaf_cnt[i] & 1), leaf_cnt[i] & 1};
    tree.resize(init_seg);

    while (q--)
    {
        vector<bool> leafs(n, 0);
        int leaf_sol = 0, curr_lfs = leaf_cnt[0];
        vector<pii> upd_res;

        int di;
        cin >> di;

        for (int i = 0; i < di; i++)
        {
            int x;
            cin >> x;
            --x;

            if (graph[x].size() == 1)
            {
                leaf_sol++;
                if (leafs[x])
                    curr_lfs++;
                else
                    leafs[x] = true;
                continue;
            }

            // otherwise we have to heavylight
            curr_lfs++;
            leaf_sol++;
            while (x != 0)
            {
                tree.update(label[top[x]], label[x]);
                upd_res.push_back({label[top[x]], label[x]});
                x = par[top[x]];
            }
        }

        if (curr_lfs % 2 == 1)
            cout << -1 << endl;
        else
        {
            pii sol = tree.query(1, id - 1);
            cout << 2 * sol.first + sol.second + leaf_sol << endl;
        }

        // now we restore
        for (pii &p : upd_res)
            tree.update(p.first, p.second);
    }
}

Compilation message (stderr)

cleaning.cpp: In function 'int init_hld(int, int)':
cleaning.cpp:124:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for (int i = 0; i < graph[v].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
cleaning.cpp: In function 'void label_hld(int, int, int, int&)':
cleaning.cpp:144:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     for (int i = 0; i < graph[v].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~

• 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