Submission #349014

#	Time	Username	Problem	Language	Result	Execution time	Memory
349014		dolphingarlic	Spring cleaning (CEOI20_cleaning)	C++14	26 / 100	155 ms	27108 KiB

cleaning

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

int n, q;
vector<int> graph[100001];
int leaves[100001], tot_leaves = 0, bad = 0;
bool is_leaf[100001];
int tin[100001], tout[100001], timer = 0, anc[100001][18];

vector<int> vtree[100001];
int ans, bit[100001];
int a[100001], l_delta[100001], subtree[100001];

void update(int pos, int val) { for (; pos <= n; pos += pos & -pos) bit[pos] += val; }

int query(int l, int r) {
    int res = 0;
    for (; r; r -= r & -r) res += bit[r];
    for (l--; l; l -= l & -l) res -= bit[l];
    return res;
}

void lca_dfs(int node, int parent = 0) {
    tin[node] = ++timer;
    for (int i = 1; i < 18; i++) anc[node][i] = anc[anc[node][i - 1]][i - 1];
    if (graph[node].size() == 1) {
        leaves[node] = 1;
        tot_leaves++;
        is_leaf[node] = true;
    }
    for (int i : graph[node]) if (i != parent) {
        anc[i][0] = node;
        lca_dfs(i, node);
        leaves[node] += leaves[i];
    }
    tout[node] = timer;
    if (leaves[node] & 1) update(tin[node], 1), update(tout[node] + 1, -1);
    else {
        update(tin[node], -1), update(tout[node] + 1, 1);
        bad++;
    }
}

bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }

int lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    for (int i = 17; ~i; i--) if (!is_ancestor(anc[u][i], v)) u = anc[u][i];
    return anc[u][0];
}

void vtree_dfs(int node, int parent = 0) {
    subtree[node] = 1;
    for (int i : vtree[node]) if (i != parent) {
        vtree_dfs(i, node);
        subtree[node] += subtree[i];
    }
    if (subtree[node] & 1) ans += query(tin[parent] + 1, tin[node]);
}

bool cmp(int u, int v) { return tin[u] < tin[v]; }

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) if (graph[i].size() > 1) {
        lca_dfs(i);
        break;
    }

    while (q--) {
        // Read query data and update original tree
        int d;
        cin >> d;
        for (int i = 0; i < d; i++) {
            cin >> a[i];
            if (is_leaf[a[i]]) is_leaf[a[i]] = false;
            else {
                leaves[a[i]]++;
                tot_leaves++;
                l_delta[a[i]]++;
            }
        }

        // Construct the virtual tree
        vector<int> nodes;
        for (int i = 0; i < d; i++) if (l_delta[a[i]] & 1) nodes.push_back(a[i]);
        sort(nodes.begin(), nodes.end(), cmp);
        int m = nodes.size();
        for (int i = 1; i < m; i++) nodes.push_back(lca(nodes[i - 1], nodes[i]));
        sort(nodes.begin(), nodes.end(), cmp);
        nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
        
        vector<int> stck;
        for (int i : nodes) {
            while (stck.size() > 1 && !is_ancestor(stck.back(), i)) {
                vtree[stck[stck.size() - 2]].push_back(stck.back());
                stck.pop_back();
            }
            stck.push_back(i);
        }
        while (stck.size() > 1) {
            vtree[stck[stck.size() - 2]].push_back(stck.back());
            stck.pop_back();
        }

        // Compute and output the answer
        if (tot_leaves & 1) cout << "-1\n";
        else {
            ans = n + d + bad - 2;
            if (stck.size()) vtree_dfs(stck[0]);
            cout << ans << '\n';
        }

        // Reset the original tree
        for (int i = 0; i < d; i++) {
            if (leaves[a[i]] == 1) is_leaf[a[i]] = true;
            else {
                leaves[a[i]]--;
                tot_leaves--;
                l_delta[a[i]]--;
            }
        }

        // Reset the vtree
        for (int i : nodes) vtree[i].clear();
    }
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 9
• Subtask 3: 9 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 17 / 17
• Subtask 7: 0 / 30