Submission #578211

#	Time	Username	Problem	Language	Result	Execution time	Memory
578211		tengiz05	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	274 ms	21636 KiB

cleaning

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

struct SegmentTree {
    int n;
    vector<int> t, lz;
    SegmentTree(int n) : n(n), t(4 * n), lz(4 * n) {}
    void push(int p, int len) {
        if (!lz[p])
            return;
        if (len > 1) {
            lz[2 * p] ^= lz[p];
            lz[2 * p + 1] ^= lz[p];
        }
        t[p] = len - t[p];
        lz[p] = 0;
    }
    void update(int p, int l, int r, int x, int y) {
        push(p, r - l);
        if (r <= x || y <= l)
            return;
        if (x <= l && r <= y) {
            lz[p] = 1;
            push(p, r - l);
            return;
        }
        int m = (l + r) / 2;
        update(2 * p, l, m, x, y);
        update(2 * p + 1, m, r, x, y);
        t[p] = t[2 * p] + t[2 * p + 1];
    }
    void update(int l, int r) {
        update(1, 0, n, l, r);
    }
    int get(int p, int l, int r, int x, int y) {
        push(p, r - l);
        if (r <= x || y <= l)
            return 0;
        if (x <= l && r <= y)
            return t[p];
        int m = (l + r) / 2;
        return get(2 * p, l, m, x, y) + get(2 * p + 1, m, r, x, y);
    }
    int get(int l, int r) {
        return get(1, 0, n, l, r);
    }
};
/*

7 4
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
5 6 6 5 4 2
1 1


4 1
1 2
1 3
1 4
2 2 2



*/
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    
    vector<vector<int>> e(n);
    vector<int> deg(n);
    
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        e[u].push_back(v);
        e[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }
    
    vector<int> c(n), in(n), out(n), par(n);
    
    int timeStamp = 0;
    int cnt = 0;
    
    function<void(int, int)> dfs = [&](int u, int p) {
        in[u] = timeStamp++;
        c[u] = deg[u] <= 1;
        cnt += c[u];
        if (p != -1) {
            e[u].erase(find(e[u].begin(), e[u].end(), p));
        }
        for (int &v : e[u]) {
            dfs(v, u);
            c[u] ^= c[v];
            if (out[v] - in[v] > out[e[u][0]] - in[e[u][0]]) {
                swap(e[u][0], v);
            }
        }
        out[u] = timeStamp;
    };
    
    dfs(0, -1);
    
    vector<int> nxt(n, 0);
    timeStamp = 0;
    dfs = [&](int u, int p) {
        in[u] = timeStamp++;
        par[u] = p;
        for (int v : e[u]) {
            nxt[v] = (v == e[u][0] ? nxt[u] : v);
            dfs(v, u);
        }
        out[u] = timeStamp;
    };
    
    dfs(0, -1);
    
    SegmentTree t(n);
    for (int i = 1; i < n; i++) {
        if (c[i]) {
            t.update(in[i], in[i] + 1);
        }
    }
    
    auto add = [&](int u) {
        for (; u != -1; u = par[nxt[u]]) {
            t.update(in[nxt[u]], in[u] + 1);
        }
    };
    
    while (q--) {
        int k;
        cin >> k;
        
        vector<int> d(k);
        for (int i = 0; i < k; i++) {
            cin >> d[i];
            d[i]--;
        }
        
        set<int> v(d.begin(), d.end());
        int leaves = cnt + k;
        for (int x : v) {
            if (deg[x] <= 1) {
                leaves--;
            }
        }
        
        if (leaves % 2 != 0) {
            cout << "-1\n";
            continue;
        }
        
        sort(d.begin(), d.end(), [&](int i, int j) {
            return in[i] > in[j];
        });
        for (int u : d) {
            if (deg[u] > 1) {
                add(u);
            }
            deg[u]++;
        }
        
        int x = t.get(1, n);
        int y = n - 1 - x;
        
        int ans = 2 * y + x + k;
        cout << ans << "\n";
        
        reverse(d.begin(), d.end());
        for (int u : d) {
            deg[u]--;
            if (deg[u] > 1) {
                add(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