Submission #1268025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268025		antonn	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	104 ms	17476 KiB

cleaning

#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;

const int N = 2e5 + 7;

int n, q, root;
vector<int> g[N];
int par[N], f[N], cnt_leaves, is_leaf[N], sz[N], heavy_son[N];

void dfs(int u, int p = 0) {
    par[u] = p;
    f[u] = 0;
    sz[u] = 1;
    for (auto v : g[u]) {
        if (v != p) {
            dfs(v, u);
            f[u] += f[v];
            sz[u] += sz[v];
            if (sz[v] > sz[heavy_son[u]]) {
                heavy_son[u] = v;
            }
        }
    }
    if (g[u].size() == 1) is_leaf[u] = 1, f[u]++, cnt_leaves++; 
}

int l[N], tt = 0, head[N], ord[N], pref[2][N];

void dfs_heavy(int u, int p) {
    l[u] = ++tt;
    ord[tt] = u;
    head[u] = p;
    if (heavy_son[u]) {
        dfs_heavy(heavy_son[u], p);
    }
    for (auto v : g[u]) {
        if (v != par[u] && v != heavy_son[u]) {
            dfs_heavy(v, v);
        }
    }
}

vector<int> events;

void update(int u) {
    while (u != 0) {
        events.push_back(l[head[u]]);
        events.push_back(l[u] + 1);
        u = par[head[u]];
    }
}

int get_sum(int s, int l, int r) {
    if (l > r) return 0;
    return pref[s][r] - pref[s][l - 1];
}

int get() {
    sort(events.begin(), events.end());
    //events.resize(unique(events.begin(), events.end()) - events.begin());
    events.push_back(n + 1);
    int ans = 0;
    ans += get_sum(0, 1, events[0] - 1); 
    for (int i = 0; i + 1 < events.size(); ++i) {
        ans += get_sum((i + 1) & 1, events[i], events[i + 1] - 1);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 1; i <= n; ++i) if (g[i].size() >= 2) root = i;
    dfs(root);
    dfs_heavy(root, root);
    for (int i = 1; i <= n; ++i) f[i] %= 2;
    for (int b = 0; b < 2; ++b) {
        for (int i = 1; i <= n; ++i) {
            pref[b][i] = pref[b][i - 1] + ((f[ord[i]] ^ b) == 0);
        }
    }
    
    int id = 0;
    while (q--) {
        int m;
        cin >> m;
        events.clear();
        int here = cnt_leaves;
        vector<int> changes;
        for (int i = 0; i < m; ++i) {
            int a;
            cin >> a;
            f[a] ^= 1;
            here++;
            if (is_leaf[a] == 1) {
                update(a);
                here--;
                changes.push_back(a);
            }
            update(a);
            is_leaf[a] = 0;
        }
        if (here % 2 == 0) {
            cout << n + m + get() - 2 << "\n";
        } else {
            cout << -1 << "\n";
        }
        for (auto x : changes) is_leaf[x] = 1;
    }
    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