oj.uz

Submission #896650

# Submission time Handle Problem Language Result Execution time Memory
896650 2024-01-01T20:12:21 Z 0x34c Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 194 ms 22104 KB 
#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;

            bool ok = true;
            if (graph[x].size() == 1)
            {
                if (leafs[x])
                    curr_lfs++;
                else
                {
                    leafs[x] = true;
                    ok = false;
                }
            }
            else
                curr_lfs++;

            leaf_sol++;
            if (graph[x].size() != 1 || leafs[x] && ok)
                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

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++)
      |                     ~~^~~~~~~~~~~~~~~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:230:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  230 |             if (graph[x].size() != 1 || leafs[x] && ok)
      |                                         ~~~~~~~~~^~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 90 ms 3880 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2264 KB Output is correct
2 Correct 33 ms 2516 KB Output is correct
3 Correct 26 ms 14868 KB Output is correct
4 Correct 41 ms 11732 KB Output is correct
5 Correct 54 ms 16164 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2960 KB Output is correct
2 Correct 41 ms 3020 KB Output is correct
3 Correct 39 ms 22104 KB Output is correct
4 Correct 98 ms 21452 KB Output is correct
5 Correct 40 ms 20564 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4184 KB Output is correct
2 Correct 32 ms 3680 KB Output is correct
3 Correct 7 ms 3164 KB Output is correct
4 Correct 8 ms 3676 KB Output is correct
5 Correct 9 ms 4004 KB Output is correct
6 Correct 50 ms 4112 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 10324 KB Output is correct
2 Correct 186 ms 10448 KB Output is correct
3 Correct 147 ms 6000 KB Output is correct
4 Correct 184 ms 10800 KB Output is correct
5 Correct 177 ms 10772 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 15852 KB Output is correct
2 Correct 113 ms 18144 KB Output is correct
3 Correct 150 ms 17716 KB Output is correct
4 Correct 134 ms 18784 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 90 ms 3880 KB Output is correct
3 Correct 30 ms 2264 KB Output is correct
4 Correct 33 ms 2516 KB Output is correct
5 Correct 26 ms 14868 KB Output is correct
6 Correct 41 ms 11732 KB Output is correct
7 Correct 54 ms 16164 KB Output is correct
8 Correct 41 ms 2960 KB Output is correct
9 Correct 41 ms 3020 KB Output is correct
10 Correct 39 ms 22104 KB Output is correct
11 Correct 98 ms 21452 KB Output is correct
12 Correct 40 ms 20564 KB Output is correct
13 Correct 56 ms 4184 KB Output is correct
14 Correct 32 ms 3680 KB Output is correct
15 Correct 7 ms 3164 KB Output is correct
16 Correct 8 ms 3676 KB Output is correct
17 Correct 9 ms 4004 KB Output is correct
18 Correct 50 ms 4112 KB Output is correct
19 Correct 135 ms 10324 KB Output is correct
20 Correct 186 ms 10448 KB Output is correct
21 Correct 147 ms 6000 KB Output is correct
22 Correct 184 ms 10800 KB Output is correct
23 Correct 177 ms 10772 KB Output is correct
24 Correct 194 ms 15852 KB Output is correct
25 Correct 113 ms 18144 KB Output is correct
26 Correct 150 ms 17716 KB Output is correct
27 Correct 134 ms 18784 KB Output is correct
28 Correct 127 ms 9936 KB Output is correct
29 Correct 121 ms 18228 KB Output is correct
30 Correct 45 ms 15816 KB Output is correct
31 Correct 106 ms 21960 KB Output is correct
32 Correct 177 ms 10764 KB Output is correct
33 Correct 116 ms 15200 KB Output is correct
34 Correct 119 ms 18772 KB Output is correct
35 Correct 117 ms 18696 KB Output is correct