Submission #1218430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218430		anonymous321	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	166 ms	26948 KiB

cleaning

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

struct node {
    int cnt1 = 0;
    int cnt2 = 0;
};

struct st {
    vector<node> v;
    vector<bool> lazy;
    int as;
};

node merge (node &l, node &r) {
    return {l.cnt1 + r.cnt1, l.cnt2 + r.cnt2};
}

void push (st &seg, int i) {
    if (seg.lazy[i]) {
        int l = i*2;
        int r = i*2 + 1;
        seg.lazy[l] = !seg.lazy[l];
        seg.lazy[r] = !seg.lazy[r];
        swap(seg.v[l].cnt1, seg.v[l].cnt2);
        swap(seg.v[r].cnt1, seg.v[r].cnt2);
        seg.lazy[i] = false;
    }
}

st build (vector<node> vs) {
    int n = vs.size();
    int as = 1 << (1 + __lg(n));
    vector<node> v (as*2);
    for (int i = 0; i < n; i++) {
        v[as + i] = vs[i];
    }
    for (int i = as-1; i > 0; i--) {
        v[i] = merge(v[i*2], v[i*2 + 1]);
    }
    vector<bool> lazy (as*2, false);
    return {v, lazy, as};
}

void apply (st &seg, int l, int r, int i = 1, int lo = 0, int hi = -1) {
    if (hi == -1) hi = seg.as;
    if (lo >= r || hi <= l) return;
    if (l <= lo && hi <= r) {
        swap(seg.v[i].cnt1, seg.v[i].cnt2);
        seg.lazy[i] = !seg.lazy[i];
        return;
    }
    push(seg, i);
    int mid = (lo + hi) / 2;
    apply(seg, l, r, i*2, lo, mid);
    apply(seg, l, r, i*2 + 1, mid, hi);
    seg.v[i] = merge(seg.v[i*2], seg.v[i*2 + 1]);
}

vector<vector<int>> adj_list;

vector<int> par;
vector<bool> leaf;
vector<int> depth, sz;
vector<node> vs;
vector<int> leaf_cnt;

int dfscnt = 0;
vector<int> pos, head;

st seg;

void dfs1 (int v) {
    leaf[v] = adj_list[v].size() == 1;
    sz[v] = 1;
    int max_sz = -1;
    for (auto &it : adj_list[v]) {
        if (it == par[v]) continue;
        par[it] = v;
        depth[it] = depth[v] + 1;
        dfs1 (it);
        sz[v] += sz[it];
        leaf_cnt[v] += leaf_cnt[it];
        if (sz[it] > max_sz) {
            max_sz = sz[it];
            swap(it, adj_list[v][0]);
        }
    }
    if (leaf[v]) leaf_cnt[v]++;
    if (leaf_cnt[v] % 2 == 0) vs[v].cnt2++;
    else vs[v].cnt1++;
}

void dfs2 (int v) {
    pos[v] = dfscnt++;
    for (int i = 0; i < adj_list[v].size(); i++) {
        int it = adj_list[v][i];
        if (it == par[v]) continue;
        if (i == 0) {
            head[it] = head[v];
        } else {
            head[it] = it;
        }
        dfs2 (it);
    }
}

void invert (int a) {
    while (a != -1) {
        apply(seg, pos[head[a]], pos[a]+1);
        a = par[head[a]];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    adj_list = vector<vector<int>> (n);
    for (int i = 0; i < n-1; i++) {
        int u, v;
        cin >> u >> v;
        adj_list[u-1].push_back(v-1);
        adj_list[v-1].push_back(u-1);
    }
    vector<vector<int>> va (q);
    for (int i = 0; i < q; i++) {
        int d;
        cin >> d;
        for (int j = 0; j < d; j++) {
            int a;
            cin >> a;
            va[i].push_back(a-1);
        }
    }

    par = vector<int> (n, -1);
    leaf = vector<bool> (n, false);
    depth = vector<int> (n, 0);
    sz = vector<int> (n, 1);
    vs = vector<node> (n);
    leaf_cnt = vector<int> (n, 0);
    dfs1 (0);

    pos = vector<int> (n, 0);
    head = vector<int> (n, 0);
    dfs2 (0);
    vs[0] = {};

    vector<node> vsp (n);
    for (int i = 0; i < n; i++) {
        vsp[pos[i]] = vs[i];
    }
    seg = build(vsp);
    
    vector<int> nleafs (n, 0);
    int lc = leaf_cnt[0];
    for (int i = 0; i < q; i++) {
        for (int j = 0; j < va[i].size(); j++) {
            int v = va[i][j];
            if (!leaf[v] || nleafs[v] > 0) {
                lc++;
                invert(v);
            }
            nleafs[v]++;
        }
        int sol = seg.v[1].cnt1 + seg.v[1].cnt2 * 2 + va[i].size();
        if (lc % 2 == 1) sol = -1;
        cout << sol << "\n";
        for (int j = 0; j < va[i].size(); j++) {
            int v = va[i][j];
            if (!leaf[v] || nleafs[v] > 1) {
                lc--;
                invert(v);
            }
            nleafs[v]--;
        }
    }
    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