Submission #1230851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230851		The_Samurai	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	144 ms	29120 KiB

cleaning

#include "bits/stdc++.h"
using namespace std;

struct fenwick {
    vector<int> tree;
    int n;

    void init(int len) {
        n = len;
        tree.assign(n + 1, 0);
    }

    void upd(int i, int v) { for (i++; i <= n; i += i & (-i)) tree[i] += v; }
    
    int get(int i) {
        int sum = 0;
        for (i++; i > 0; i -= i & (-i)) sum += tree[i];
        return sum;
    }

    int get(int l, int r) {
        return get(r) - get(l - 1);
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n, q;
    cin >> n >> q;
    vector<vector<int>> g(2 * n);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    const int lg = 17;
    vector jump(lg, vector(n + 1, 0));
    vector<int> tin(n + 1), tout(n + 1), ord(n + 1);
    vector<int> depth(n + 1), rem(n + 1);
    vector<pair<int, int>> cnt(n + 1);
    int ans = 0, z = 0, root = 1;
    while (g[root].size() == 1) root++;

    auto dfs = [&](auto &dfs, int u, int p) -> void {
        for (int i = 1; i < lg; i++) {
            jump[i][u] = jump[i - 1][jump[i - 1][u]];
            if (!jump[i][u]) break;
        }
        tin[u] = tout[u] = z++;
        ord[tin[u]] = u;
        for (int v: g[u]) {
            if (v == p) continue;
            jump[0][v] = u;
            depth[v] = depth[u] + 1;
            dfs(dfs, v, u);
            rem[u] += rem[v];
            tout[u] = tout[v];
        }
        rem[u] = 2 - rem[u] % 2;
        if (g[u].size() == 1) rem[u] = 1;
        if (u != root) ans += rem[u];
    };
    dfs(dfs, root, 0);

    auto dfs2 = [&](auto &dfs2, int u, int p) -> void {
        for (int v: g[u]) {
            if (v == p) continue;
            cnt[v] = cnt[u];
            if (rem[v] == 1) cnt[v].first++;
            else cnt[v].second++;
            dfs2(dfs2, v, u);
        }
    };
    dfs2(dfs2, root, 0);

    auto isPar = [&](int u, int v) -> bool { return tin[u] <= tin[v] and tout[v] <= tout[u]; };
    auto lca = [&](int u, int v) -> int {
        if (isPar(u, v)) return u;
        if (isPar(v, u)) return v;
        for (int i = lg - 1; i >= 0; i--) {
            if (jump[i][u] and !isPar(jump[i][u], v)) u = jump[i][u];
        }
        return jump[0][u];
    };

    int old_ans = ans;
    vector<int> shit(n + 1);
    vector<bool> vis(n + 1);
    fenwick fw; fw.init(n + 1);

    while (q--) {
        int ln;
        cin >> ln;
        ans = old_ans + ln;
        vector<int> v(ln), vec;
        for (int &x: v) cin >> x;
        for (int x: v) shit[x]++;
        for (int x: v) {
            if (vis[x]) continue;
            vis[x] = true;
            if (g[x].size() == 1) shit[x]--;
            if (shit[x] % 2) vec.emplace_back(x);
        }
        sort(vec.begin(), vec.end(), [&](int a, int b) {
            return tin[a] < tin[b];
        });
        set<int> st;
        for (int x: vec) st.insert(tin[x]), fw.upd(tin[x], 1);
        for (int i = 1; i < vec.size(); i++) st.insert(tin[lca(vec[i - 1], vec[i])]);
        auto dfs = [&](auto &dfs, int u, int p) -> void {
            st.erase(tin[u]);
            while (true) {
                auto it = st.lower_bound(tin[u]);
                if (it == st.end() or *it > tout[u]) break;
                int v = ord[*it];
                dfs(dfs, v, u);
            }
            if (fw.get(tin[u], tout[u]) % 2 == 0) return;
            ans += (cnt[u].first - cnt[p].first) - (cnt[u].second - cnt[p].second);
        };
        // for (int x: st) cout << ord[x] << ' ' << x << ' ' << tout[ord[x]] << endl;
        // for (int x: vec) cout << x << ' ' << tin[x] << ' ' << tout[x] << endl;
        // cout << '\t' << st.size() << ' ' << vec.size() << endl;
        while (!st.empty()) {
            dfs(dfs, ord[*st.begin()], root);
        }
        // cout << st.size() << endl;
        if ((fw.get(tin[root], tout[root]) + rem[root]) % 2) cout << "-1\n";
        else cout << ans << '\n';


        for (int x: v) shit[x] = vis[x] = 0;
        for (int x: vec) fw.upd(tin[x], -1);
    }
}

• 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