oj.uz

Submission #349018

# Submission time Handle Problem Language Result Execution time Memory
349018 2021-01-16T10:43:43 Z dolphingarlic Spring cleaning (CEOI20_cleaning) C++14
26 / 100
 151 ms 25572 KB 
#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 (anc[u][i] && !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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Incorrect 50 ms 7788 KB Output isn't correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 6384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7024 KB Output is correct
2 Correct 30 ms 7024 KB Output is correct
3 Correct 74 ms 25324 KB Output is correct
4 Correct 108 ms 25572 KB Output is correct
5 Correct 69 ms 23148 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 8632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 13420 KB Output is correct
2 Incorrect 103 ms 13568 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 18424 KB Output is correct
2 Correct 146 ms 20716 KB Output is correct
3 Correct 151 ms 21164 KB Output is correct
4 Correct 137 ms 20076 KB Output is correct

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Incorrect 50 ms 7788 KB Output isn't correct