oj.uz

Submission #702354

# Submission time Handle Problem Language Result Execution time Memory
702354 2023-02-23T16:24:20 Z Cyanmond Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 546 ms 29356 KB 
#include <bits/stdc++.h>

using i64 = long long;

struct HLD {
    int n;
    std::vector<std::vector<int>> tree;
    std::vector<int> st, in, out, head, parent;

    HLD(std::vector<std::vector<int>> tree_, int root) {
        tree = tree_;
        n = tree.size();
        st.resize(n);
        in.resize(n);
        out.resize(n);
        head.resize(n);
        parent.resize(n);
        dfs1(root, -1);
        int x = 0;
        head[root] = root;
        dfs2(root, -1, x);
    }

    void dfs1(int v, int p) {
        parent[v] = p;
        st[v] = 1;
        for (int &t : tree[v]) {
            if (t == p) {
                continue;
            }
            dfs1(t, v);
            st[v] += st[t];
            if (st[tree[v][0]] < st[t]) {
                std::swap(tree[v][0], t);
            }
        }
    }

    void dfs2(int v, int p, int &id) {
        in[v] = id++;
        for (const int t : tree[v]) {
            if (t == p) {
                continue;
            }
            head[t] = tree[v][0] == t ? head[v] : t;
            dfs2(t, v, id);
        }
        out[v] = id;
    }

    template <class F>
    void query(int v, const F &func) {
        while (v != -1) {
            func(in[head[v]], in[v] + 1);
            v = parent[head[v]];
        }
    }
};

struct node {
    int a, b;
};
node op(node a, node b) {
    return {a.a + b.a, a.b + b.b};
}
node e() {
    return {0, 0};
}
node map(bool x, node b) {
    if (x) std::swap(b.a, b.b);
    return b;
}
bool composite(bool x, bool y) {
    return x xor y;
}
bool id() {
    return false;
}
class lazySegtree {
    int n, size, lg;
    std::vector<node> data;
    std::vector<bool> lazy;

    void update(int i) {
        data[i] = op(data[2 * i], data[2 * i + 1]);
    }
    void cv(int i, bool f) {
        data[i] = map(f, data[i]);
        if (i < size) {
            lazy[i] = composite(f, lazy[i]);
        }
    }
    void push(int i) {
        cv(2 * i, lazy[i]);
        cv(2 * i + 1, lazy[i]);
        lazy[i] = id();
    }
    public:

    lazySegtree(int n_) {
        n = n_;
        size = 1;
        lg = 0;
        while (size < n) {
            ++lg;
            size *= 2;
        }
        data.assign(2 * size, e());
        lazy.assign(size, id());
    }

    void set(int i, node v) {
        i += size;
        for (int d = lg; d >= 1; --d) {
            push(i >> d);
        }
        data[i] = v;
        for (int d = 1; d <= lg; ++d) {
            update(i >> d);
        }
    }

    node fold(int l, int r) {
        l += size, r += size;
        for (int d = lg; d >= 1; --d) {
            if (((l >> d) << d) != l) push(l >> d);
            if (((r >> d) << d) != r) push((r - 1) >> d);
        }
        node retL = e(), retR = e();
        while (l < r) {
            if (l & 1) retL = op(retL, data[l++]);
            if (r & 1) retR = op(data[--r], retR);
            l /= 2;
            r /= 2;
        }
        return op(retL, retR);
    }

    void apply(int l, int r, bool f) {
        l += size, r += size;
        for (int d = lg; d >= 1; --d) {
            if (((l >> d) << d) != l) push(l >> d);
            if (((r >> d) << d) != r) push((r - 1) >> d);
        }
        int l2 = l, r2 = r;
        while (l < r) {
            if (l & 1) cv(l++, f);
            if (r & 1) cv(--r, f);
            l /= 2;
            r /= 2;
        }
        l = l2, r = r2;
        for (int d = 1; d <= lg; ++d) {
            if (((l >> d) << d) != l) update(l >> d);
            if (((r >> d) << d) != r) update((r - 1) >> d);
        }
    }
};

int main() {
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N - 1), B(N - 1);
    std::vector<std::vector<int>> baseTree(N);
    for (int i = 0; i < N - 1; ++i) {
        std::cin >> A[i] >> B[i];
        --A[i], --B[i];
        baseTree[A[i]].push_back(B[i]);
        baseTree[B[i]].push_back(A[i]);
    }
    std::vector<int> D(Q);
    std::vector<std::vector<int>> L(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> D[i];
        L[i].resize(D[i]);
        for (int &e : L[i]) {
            std::cin >> e;
            --e;
        }
    }
    std::vector<int> degree(N);
    for (int i = 0; i < N; ++i) {
        degree[i] = (int)baseTree[i].size();
    }
    const int nonLeafV = (std::max_element(degree.begin(), degree.end()) - degree.begin());
    const int countBaseLeaf = std::count(degree.begin(), degree.end(), 1);
    std::vector<bool> isEven(N);
    std::vector<int> parent(N);
    auto dfs = [&](auto &&self, const int v, const int p) -> bool {
        parent[v] = p;

        bool res = false;
        if (baseTree[v].size() == 1) {
            res = true;
        }
        for (const int t : baseTree[v]) {
            if (t == p) {
                continue;
            }
            res ^= self(self, t, v);
        }
        isEven[v] = not res;
        return res;
    };
    dfs(dfs, nonLeafV, -1);
    int baseAnswer = N - 1;

    HLD hld(baseTree, nonLeafV);
    lazySegtree seg(N);
    for (int i = 0; i < N; ++i) {
        node v = {isEven[i] ? 1 : 0, isEven[i] ? 0 : 1};
        seg.set(hld.in[i], v);
    }
    assert(seg.fold(1, N).a == std::count(isEven.begin(), isEven.end(), true) - isEven[nonLeafV]);

    for (int q = 0; q < Q; ++q) {
        int countLeaf = countBaseLeaf;
        int answer = baseAnswer;
        auto toup = [&](const int v) -> void {
            hld.query(v, [&](int l, int r) {
                seg.apply(l, r, true);
            });
        };

        for (int i = 0; i < D[q]; ++i) {
            const int v = L[q][i];
            if (degree[v] != 1) {
                ++countLeaf;
                ++answer;
                toup(v);
            } else {
                ++answer;
            }
            ++degree[v];
        }
        answer += seg.fold(1, N).a;
        if (countLeaf % 2 == 1) {
            answer = -1;
        }
        std::cout << answer << std::endl;

        for (int i = 0; i < D[q]; ++i) {
            const int v = L[q][i];
            --degree[v];
            if (degree[v] != 1) {
                toup(v);
            }
        }
    }
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 225 ms 5620 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 1636 KB Output is correct
2 Correct 100 ms 1632 KB Output is correct
3 Correct 100 ms 22144 KB Output is correct
4 Correct 148 ms 16052 KB Output is correct
5 Correct 191 ms 22340 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 2248 KB Output is correct
2 Correct 67 ms 2260 KB Output is correct
3 Correct 114 ms 25632 KB Output is correct
4 Correct 191 ms 23712 KB Output is correct
5 Correct 99 ms 23292 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 5736 KB Output is correct
2 Correct 86 ms 5044 KB Output is correct
3 Correct 22 ms 4604 KB Output is correct
4 Correct 23 ms 4860 KB Output is correct
5 Correct 25 ms 4916 KB Output is correct
6 Correct 90 ms 5240 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 18144 KB Output is correct
2 Correct 448 ms 14668 KB Output is correct
3 Correct 351 ms 8140 KB Output is correct
4 Correct 437 ms 14784 KB Output is correct
5 Correct 433 ms 14676 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 27720 KB Output is correct
2 Correct 356 ms 28584 KB Output is correct
3 Correct 445 ms 29332 KB Output is correct
4 Correct 468 ms 29356 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 225 ms 5620 KB Output is correct
3 Correct 104 ms 1636 KB Output is correct
4 Correct 100 ms 1632 KB Output is correct
5 Correct 100 ms 22144 KB Output is correct
6 Correct 148 ms 16052 KB Output is correct
7 Correct 191 ms 22340 KB Output is correct
8 Correct 68 ms 2248 KB Output is correct
9 Correct 67 ms 2260 KB Output is correct
10 Correct 114 ms 25632 KB Output is correct
11 Correct 191 ms 23712 KB Output is correct
12 Correct 99 ms 23292 KB Output is correct
13 Correct 132 ms 5736 KB Output is correct
14 Correct 86 ms 5044 KB Output is correct
15 Correct 22 ms 4604 KB Output is correct
16 Correct 23 ms 4860 KB Output is correct
17 Correct 25 ms 4916 KB Output is correct
18 Correct 90 ms 5240 KB Output is correct
19 Correct 421 ms 18144 KB Output is correct
20 Correct 448 ms 14668 KB Output is correct
21 Correct 351 ms 8140 KB Output is correct
22 Correct 437 ms 14784 KB Output is correct
23 Correct 433 ms 14676 KB Output is correct
24 Correct 546 ms 27720 KB Output is correct
25 Correct 356 ms 28584 KB Output is correct
26 Correct 445 ms 29332 KB Output is correct
27 Correct 468 ms 29356 KB Output is correct
28 Correct 312 ms 14128 KB Output is correct
29 Correct 254 ms 24396 KB Output is correct
30 Correct 163 ms 23120 KB Output is correct
31 Correct 190 ms 24524 KB Output is correct
32 Correct 439 ms 15280 KB Output is correct
33 Correct 255 ms 19548 KB Output is correct
34 Correct 269 ms 24740 KB Output is correct
35 Correct 307 ms 24012 KB Output is correct