Submission #830067

#	Time	Username	Problem	Language	Result	Execution time	Memory
830067		t6twotwo	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	173 ms	19004 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int M, leaves, timer;
vector<bool> leaf;
vector<int> f, par, sz, in, top, c0, c1, lz;
vector<vector<int>> adj;
void init(int x) {
    if (adj[x].size() == 1) {
        f[x] = 1;
        leaf[x] = 1;
        leaves ^= 1;
    }
    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;
        init(y);
        f[x] ^= f[y];
        sz[x] += sz[y];
        if (sz[y] > sz[adj[x][0]]) {
            swap(y, adj[x][0]);
        }
    }
}
void dfs(int x) {
    in[x] = timer++;
    for (int y : adj[x]) {
        top[y] = adj[x][0] == y ? top[x] : y;
        dfs(y);
    }
}
void apply(int p, int v) {
    if (v == 0) {
        return;
    }
    swap(c0[p], c1[p]);
    lz[p] ^= 1;
}
void push(int p) {
    apply(p * 2, lz[p]);
    apply(p * 2 + 1, lz[p]);
    lz[p] = 0;
}
void pull(int p) {
    c0[p] = c0[p * 2] + c0[p * 2 + 1];
    c1[p] = c1[p * 2] + c1[p * 2 + 1];
}
void upd(int p, int l, int r, int L, int R) {
    if (R <= l || r <= L) {
        return;
    }
    if (L <= l && r <= R) {
        apply(p, 1);
        return;
    }
    int m = (l + r + 1) / 2;
    push(p);
    upd(p * 2, l, m, L, R);
    upd(p * 2 + 1, m, r, L, R);
    pull(p);
}
void build(vector<int> &a) {
    int N = a.size();
    M = 2 << __lg(N);
    c0.resize(2 * M);
    c1.resize(2 * M);
    lz.resize(2 * M);
    for (int i = 0; i < N; i++) {
        if (a[i] == 0) {
            c0[in[i] + M] = 1;
        } else {
            c1[in[i] + M] = 1;
        }
    }
    for (int i = M - 1; i; i--) {
        pull(i);
    }
}
void update(int s) {
    while (s != -1) {
        upd(1, 0, M, in[top[s]], in[s] + 1);
        s = par[top[s]];
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    adj.resize(N);
    for (int i = 0; i < N - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f.resize(N);
    in.resize(N);
    sz.resize(N);
    top.resize(N);
    par.resize(N, -1);
    leaf.resize(N);
    init(0);
    dfs(0);
    build(f);
    auto l = leaf;
    while (Q--) {
        int D;
        cin >> D;
        vector<int> p(D);
        for (int i = 0; i < D; i++) {
            cin >> p[i];
            p[i]--;
            if (l[p[i]]) {
                l[p[i]] = 0;
                leaves ^= 1;
            } else {
                update(p[i]);
            }
        }
        leaves ^= D & 1;
        if (leaves == 1) {
            cout << -1 << "\n";
        } else {
            cout << N + D + c0[1] - 2 << "\n";
        }
        leaves ^= D & 1;
        for (int i = 0; i < D; i++) {
            if (leaf[p[i]] && !l[p[i]]) {
                l[p[i]] = 1;
                leaves ^= 1;
            } else {
                update(p[i]);
            }
        }
    }
    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