Submission #924065

#	Time	Username	Problem	Language	Result	Execution time	Memory
924065		Camillus	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	150 ms	23632 KiB

cleaning

/// @author Camillus
#include <bits/stdc++.h>
using namespace std;

static constexpr int maxn = 1 << 17;

vector<int> g[maxn];
int p[maxn];
int sz[maxn];
int cnt[maxn];

int root = 0;

void dfs1(int u) {
    sz[u] = 1;

    auto it = find(g[u].begin(), g[u].end(), p[u]);
    if (it != g[u].end()) g[u].erase(it);

    if (g[u].empty()) {
        cnt[u] = 1;
        return;
    }

    for (int v : g[u]) {
        p[v] = u;
        dfs1(v);
        sz[u] += sz[v];
        cnt[u] += cnt[v];
    }

    int &f = g[u].front();
    for (int &v : g[u]) {
        if (sz[v] > sz[f]) {
            swap(f, v);
        }
    }
}


int tin[maxn];
int head[maxn];
int timer = 0;

void dfs2(int u) {
    tin[u] = timer++;

    if (head[u] == 0) {
        head[u] = u;
    }

    if (!g[u].empty()) {
        head[g[u].front()] = head[u];
    }

    for (int v : g[u]) {
        dfs2(v);
    }
}

namespace st {
    using value_t = array<int, 2>;
    value_t cnt[maxn * 2 - 1];
    bool reversed[maxn * 2 - 1];

    constexpr value_t merge(const value_t &first, const value_t &second) {
        return {first[0] + second[0], first[1] + second[1]};
    }

    inline void apply(int x) {
        swap(cnt[x][0], cnt[x][1]);
        reversed[x] ^= 1;
    }

    inline void push(int x) {
        if (reversed[x]) {
            apply(x * 2 + 1);
            apply(x * 2 + 2);
            reversed[x] = false;
        }
    }

    void reverse(int l, int r, int x = 0, int lx = 0, int rx = maxn) {
        if (l >= rx || lx >= r) {
            return;
        }

        if (l <= lx && rx <= r) {
            apply(x);
            return;
        }

        push(x);

        reverse(l, r, x * 2 + 1, lx, (lx + rx) / 2);
        reverse(l, r, x * 2 + 2, (lx + rx) / 2, rx);

        cnt[x] = merge(cnt[x * 2 + 1], cnt[x * 2 + 2]);
    }

    value_t get(int i, int x = 0, int lx = 0, int rx = maxn) {
        if (rx - lx == 1) {
            return cnt[x];
        }

        push(x);

        if (i < (lx + rx) / 2) {
            return get(i, x * 2 + 1, lx, (lx + rx) / 2);
        } else {
            return get(i, x * 2 + 2, (lx + rx) / 2, rx);
        }
    }

    void build(int n) {
        for (int u = 1; u <= n; u++) {
            int x = maxn + tin[u] - 1;
            cnt[x][::cnt[u] % 2] = 1;
        }

        for (int x = maxn - 2; x >= 0; x--) {
            cnt[x] = merge(cnt[x * 2 + 1], cnt[x * 2 + 2]);
        }
    }
} // namespace st

void reverse_path(int u) {
    while (true) {
        int v = head[u];

        st::reverse(tin[v], tin[u] + 1);

        u = v;

        if (u == root) {
            break;
        } else {
            u = p[u];
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int u = 1; u <= n; u++) {
        if (g[u].size() > 1) {
            root = u;
        }
    }

    dfs1(root);
    dfs2(root);

    st::build(n);

    while (q--) {
        int d;
        cin >> d;

        map<int, int> c;

        for (int i = 0; i < d; i++) {
            int u;
            cin >> u;

            c[u] ^= 1;
        }

        for (auto &[u, k] : c) {
            if (g[u].size() == 0) {
                k ^= 1;
            }
        }

        for (auto &[u, k] : c) {
            if (k) {
                reverse_path(u);
            }
        }

        auto result = st::cnt[0];

        result[1] += d;

        if (st::get(0)[1]) {
            cout << -1 << '\n';
        } else {
            cout << (result[0] - 1) * 2 + result[1] << '\n';
        }

        for (auto &[u, k] : c) {
            if (k) {
                reverse_path(u);
            }
        }
    }
    return 0;
}

• 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