Submission #702354

#	Time	Username	Problem	Language	Result	Execution time	Memory
702354		Cyanmond	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	546 ms	29356 KiB

cleaning

#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
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30