Submission #1228270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228270		Turkhuu	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	155 ms	20804 KiB

cleaning

#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
bool seen[N];
int n, par[N], zleaf[N], sz[N], top[N], timer, pos[N], lvl[N], se[4 * N], so[4 * N], lz[4 * N], a[N];
vector<int> ch[N];
void init(int x) {
    sz[x] = 1;
    if ((int)ch[x].size() + (x != 1) == 1) zleaf[x] = 1;
    for (int& y : ch[x]) {
        lvl[y] = lvl[x] + 1;
        ch[y].erase(find(ch[y].begin(), ch[y].end(), par[y] = x));
        init(y);
        sz[x] += sz[y];
        zleaf[x] ^= zleaf[y];
        if (sz[y] > sz[ch[x][0]]) swap(ch[x][0], y);
    }
}
void dfs(int x) {
    a[pos[x] = ++timer] = zleaf[x];
    for (int y : ch[x]) {
        top[y] = ch[x][0] == y ? top[x] : y;
        dfs(y);
    }
}
void upd(int x) {
    swap(se[x], so[x]), lz[x] ^= 1;
}
void pull(int x) {
    se[x] = se[x * 2] + se[x * 2 + 1];
    so[x] = so[x * 2] + so[x * 2 + 1];
}
void push(int x) {
    if (lz[x])
        upd(x * 2), upd(x * 2 + 1), lz[x] = 0;
}
void build(int x, int l, int r) {
    if (l == r) {a[l] % 2 ? so[x] = 1 : se[x] = 1; return;}
    int m = (l + r) / 2;
    build(x * 2, l, m), build(x * 2 + 1, m + 1, r), pull(x);
}
void upd(int x, int l, int r, int L, int R) {
    if (R < l || r < L) return;
    if (L <= l && r <= R) {upd(x); return;}
    int m = (l + r) / 2;
    push(x), upd(x * 2, l, m, L, R), upd(x * 2 + 1, m + 1, r, L, R), pull(x);
}
void flip(int x) {
    for (; x; x = par[top[x]])
        upd(1, 1, n, pos[top[x]], pos[x]);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    FOR(i, 1, n - 1) {
        int a, b;
        cin >> a >> b;
        ch[a].push_back(b);
        ch[b].push_back(a);
    }
    top[1] = 1, init(1), dfs(1), build(1, 1, n);
    while (q--) {
        int D;
        cin >> D;
        int Zleaf = zleaf[1] ^ D;
        vector<int> u(D);
        for (auto& x : u) {
            cin >> x;
            if (!seen[x] && ch[x].size() + (x != 1) == 1)
                seen[x] = 1, Zleaf ^= 1;
            else flip(x);
        }
        cout << (Zleaf % 2 ? -1 : n - 1 + D + se[1] - 1) << "\n";
        for (int x : u) {
            if (seen[x] && ch[x].size() + (x != 1) == 1)
                seen[x] = 0;
            else flip(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