Submission #784456

#	Time	Username	Problem	Language	Result	Execution time	Memory
784456		t6twotwo	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	203 ms	25664 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    vector<int> deg(N);
    vector<vector<int>> adj(N);
    for (int i = 0; i < N - 1; i++) {
        int x, y;
        cin >> x >> y;
        deg[--x]++;
        deg[--y]++;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    vector<int> v(N), par(N, -1), dep(N), sz(N);
    int cnt = 0, leaves = 0;
    auto init = [&](auto init, int x) -> void {
        if (deg[x] == 1) {
            v[x] = 1;
            leaves++;
        }
        if (par[x] != -1) {
            adj[x].erase(find(adj[x].begin(), adj[x].end(), par[x]));
        }
        sz[x] = 1;
        for (int &y : adj[x]) {
            par[y] = x;
            dep[y] = dep[x] + 1;
            init(init, y);
            sz[x] += sz[y];
            v[x] ^= v[y];
            if (sz[y] > sz[adj[x][0]]) {
                swap(y, adj[x][0]);
            }
        }
        cnt += v[x];
    };
    init(init, 0);
    int K = 2 << __lg(N - 1);
    vector<int> top(N), in(N), lazy(2 * K), s(2 * K), t(2 * K);
    int timer = 0;
    auto dfs = [&](auto dfs, int x) -> void {
        in[x] = timer++;
        s[in[x] + K] = v[x];
        t[in[x] + K] = 1;
        for (int y : adj[x]) {
            top[y] = y == adj[x][0] ? top[x] : y;
            dfs(dfs, y);
        }
    };
    dfs(dfs, 0);
    auto apply = [&](int p, int z) {
        if (z) {
            s[p] = t[p] - s[p];
            lazy[p] ^= 1;
        }
    };
    auto pull = [&](int p) {
        s[p] = s[p * 2] + s[p * 2 + 1];
    };
    auto push = [&](int p) {
        apply(p * 2, lazy[p]);
        apply(p * 2 + 1, lazy[p]);
        lazy[p] = 0;
    };
    auto update = [&](auto f, int p, int l, int r, int L, int R) -> void {
        if (R <= l || r <= L) {
            return;
        }
        if (L <= l && r <= R) {
            apply(p, 1);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        f(f, p * 2, l, m, L, R);
        f(f, p * 2 + 1, m, r, L, R);
        pull(p);
    };
    for (int i = K - 1; i; i--) {
        pull(i);
        t[i] = t[i * 2] + t[i * 2 + 1];
    }
    while (Q--) {
        int D;
        cin >> D;
        vector<int> a(D);
        for (int &p : a) {
            cin >> p;
            p--;
            if (deg[p]++ != 1) {
                leaves++;
                int x = p;
                while (x != -1) {
                    update(update, 1, 0, K, in[top[x]], in[x] + 1);
                    x = par[top[x]];
                }
            }
        }
        if (leaves % 2 == 1) {
            cout << -1 << "\n";
        } else {
            cout << 2 * (N - 1) - s[1] + D << "\n";
        }
        for (int p : a) {
            if (--deg[p] != 1) {
                leaves--;
                int x = p;
                while (x != -1) {
                    update(update, 1, 0, K, in[top[x]], in[x] + 1);
                    x = par[top[x]];
                }
            }
        }
    }
    return 6/22;
}

• 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