oj.uz

Submission #866040

# Submission time Handle Problem Language Result Execution time Memory
866040 2023-10-25T10:26:59 Z boris_mihov Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 162 ms 29804 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <stack>

typedef long long llong;
const int MAXN = 200000 + 10;
const int MOD = 1e9 + 7;
const int INF = 2e9;

int n, q;
struct SegmentTree
{
    struct Node
    {
        int cntODD;
        int cntEVEN;
        bool lazy;

        Node()
        {
            cntODD = 0;
            cntEVEN = 0;
            lazy = false;
        }
    };

    Node tree[4*MAXN];
    Node combine(Node left, Node right)
    {
        Node res;
        res.cntODD = left.cntODD + right.cntODD;
        res.cntEVEN = left.cntEVEN + right.cntEVEN;
        return res;
    }

    void push(int node, int l, int r)
    {
        if (!tree[node].lazy)
        {
            return;
        }

        std::swap(tree[node].cntODD, tree[node].cntEVEN);
        if (l < r)
        {
            tree[2*node].lazy ^= 1;
            tree[2*node + 1].lazy ^= 1;
        }

        tree[node].lazy = false;
    }

    void build(int l, int r, int node, std::vector <int> &tour, bool par[])
    {
        if (l == r)
        {
            if (par[tour[l]]) tree[node].cntODD = 1;
            else tree[node].cntEVEN = 1;
            return;
        }

        int mid = (l + r) / 2;
        build(l, mid, 2*node, tour, par);
        build(mid + 1, r, 2*node + 1, tour, par);
        tree[node] = combine(tree[2*node], tree[2*node + 1]);
    }

    void update(int l, int r, int node, int queryL, int queryR)
    {
        push(node, l, r);
        if (r < queryL || queryR < l)
        {
            return;
        }

        if (queryL <= l && r <= queryR)
        {
            tree[node].lazy ^= 1;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        update(l, mid, 2*node, queryL, queryR);
        update(mid + 1, r, 2*node + 1, queryL, queryR);
        tree[node] = combine(tree[2*node], tree[2*node + 1]);
    }

    int count()
    {
        return tree[1].cntEVEN;
    }

    void build(std::vector <int> tour, bool par[])
    {
        assert(tour.size() == n);
        build(0, n - 1, 1, tour, par);
    }

    void update(int l, int r)
    {
        update(0, n - 1, 1, l, r);
    }
};

int cnt;
int par[MAXN];
bool res[MAXN];
bool was[MAXN];
SegmentTree tree;
bool isLeaf[MAXN];
std::vector <int> g[MAXN];
std::vector <int> tour;
int segPos[MAXN];
int heavy[MAXN];
int head[MAXN];
int sz[MAXN];

int dfs(int node, int p)
{
    par[node] = p;
    if (g[node].size() == 1)
    {
        cnt ^= 1;
        isLeaf[node] = true;
        res[node] = 1;
        return res[node];
    }

    res[node] = 0;
    for (const int &u : g[node])
    {
        if (u == p)
        {
            continue;
        }

        res[node] ^= dfs(u, node);
    }

    return res[node];
}

void initDFS(int node)
{
    sz[node] = 1;
    heavy[node] = 0;
    for (const int &u : g[node])
    {
        if (u == par[node])
        {
            continue;
        }

        initDFS(u);
        sz[node] += sz[u];
        if (sz[u] > sz[heavy[node]])
        {
            heavy[node] = u;
        }
    }
}

void buildTour(int node, int h)
{
    head[node] = h;
    tour.push_back(node);
    segPos[node] = tour.size() - 1;
    if (heavy[node] != 0)
    {
        buildTour(heavy[node], h);
    }

    for (const int &u : g[node])
    {
        if (u == par[node] || u == heavy[node])
        {
            continue;
        }

        buildTour(u, u);
    }
}

void climb(int node)
{
    tree.update(segPos[head[node]], segPos[node]);
    if (par[head[node]] != 0)
    {
        climb(par[head[node]]);
    } else
    {
        cnt ^= 1;
    }
}

int a[MAXN];
void solve()
{  
    int root = 1;
    if (g[1].size() == 1) root = g[1][0];
    dfs(root, 0);

    initDFS(root);
    buildTour(root, root);
    tree.build(tour, res);

    for (int i = 1 ; i <= q ; ++i)
    {
        int d;
        std::cin >> d;
        for (int j = 1 ; j <= d ; ++j)
        {
            std::cin >> a[j];
            if (isLeaf[a[j]] && !was[a[j]]) was[a[j]] = true;
            else 
            {
                climb(a[j]);
            }
        }

        if (cnt) std::cout << -1 << '\n';
        else std::cout << n + d + tree.count() - 2 << '\n';

        for (int j = 1 ; j <= d ; ++j)
        {
            if (isLeaf[a[j]] && was[a[j]]) was[a[j]] = false;
            else 
            {
                climb(a[j]);
            }
        }
    }
}   

void input()
{
    std::cin >> n >> q;
    for (int i = 2 ; i <= n ; ++i)
    {
        int u, v;
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from cleaning.cpp:4:
cleaning.cpp: In member function 'void SegmentTree::build(std::vector<int>, bool*)':
cleaning.cpp:100:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |         assert(tour.size() == n);
      |                ~~~~~~~~~~~~^~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 79 ms 19840 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 19216 KB Output is correct
2 Correct 41 ms 19032 KB Output is correct
3 Correct 24 ms 23640 KB Output is correct
4 Correct 64 ms 22228 KB Output is correct
5 Correct 48 ms 23636 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 19548 KB Output is correct
2 Correct 39 ms 19548 KB Output is correct
3 Correct 41 ms 29388 KB Output is correct
4 Correct 105 ms 28300 KB Output is correct
5 Correct 33 ms 28332 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 20316 KB Output is correct
2 Correct 29 ms 19800 KB Output is correct
3 Correct 9 ms 19804 KB Output is correct
4 Correct 12 ms 20064 KB Output is correct
5 Correct 11 ms 20568 KB Output is correct
6 Correct 49 ms 20388 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 21720 KB Output is correct
2 Correct 160 ms 21720 KB Output is correct
3 Correct 126 ms 20312 KB Output is correct
4 Correct 154 ms 21720 KB Output is correct
5 Correct 152 ms 21708 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 23412 KB Output is correct
2 Correct 77 ms 26012 KB Output is correct
3 Correct 114 ms 27020 KB Output is correct
4 Correct 120 ms 27860 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 79 ms 19840 KB Output is correct
3 Correct 41 ms 19216 KB Output is correct
4 Correct 41 ms 19032 KB Output is correct
5 Correct 24 ms 23640 KB Output is correct
6 Correct 64 ms 22228 KB Output is correct
7 Correct 48 ms 23636 KB Output is correct
8 Correct 38 ms 19548 KB Output is correct
9 Correct 39 ms 19548 KB Output is correct
10 Correct 41 ms 29388 KB Output is correct
11 Correct 105 ms 28300 KB Output is correct
12 Correct 33 ms 28332 KB Output is correct
13 Correct 58 ms 20316 KB Output is correct
14 Correct 29 ms 19800 KB Output is correct
15 Correct 9 ms 19804 KB Output is correct
16 Correct 12 ms 20064 KB Output is correct
17 Correct 11 ms 20568 KB Output is correct
18 Correct 49 ms 20388 KB Output is correct
19 Correct 98 ms 21720 KB Output is correct
20 Correct 160 ms 21720 KB Output is correct
21 Correct 126 ms 20312 KB Output is correct
22 Correct 154 ms 21720 KB Output is correct
23 Correct 152 ms 21708 KB Output is correct
24 Correct 133 ms 23412 KB Output is correct
25 Correct 77 ms 26012 KB Output is correct
26 Correct 114 ms 27020 KB Output is correct
27 Correct 120 ms 27860 KB Output is correct
28 Correct 106 ms 22720 KB Output is correct
29 Correct 101 ms 27008 KB Output is correct
30 Correct 50 ms 24652 KB Output is correct
31 Correct 87 ms 29804 KB Output is correct
32 Correct 162 ms 22716 KB Output is correct
33 Correct 106 ms 25560 KB Output is correct
34 Correct 116 ms 27280 KB Output is correct
35 Correct 118 ms 27204 KB Output is correct