oj.uz

Submission #349021

# Submission time Handle Problem Language Result Execution time Memory
349021 2021-01-16T10:52:31 Z dolphingarlic Spring cleaning (CEOI20_cleaning) C++14
37 / 100
 149 ms 26080 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];

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 = 1, 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) {
    for (int i : vtree[node]) if (i != parent) {
        vtree_dfs(i, node);
        l_delta[node] += l_delta[i];
    }
    if (l_delta[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);
    }
    lca_dfs();

    while (q--) {
        // Read query data and update original tree
        int d;
        cin >> d;
        vector<int> nodes;
        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]]++;
                nodes.push_back(a[i]);
            }
        }

        // Construct the virtual tree
        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--;
            }
        }

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

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 51 ms 7788 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6892 KB Output is correct
2 Correct 38 ms 6892 KB Output is correct
3 Correct 66 ms 17540 KB Output is correct
4 Correct 74 ms 15076 KB Output is correct
5 Correct 99 ms 18660 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 7532 KB Output is correct
2 Correct 57 ms 7532 KB Output is correct
3 Correct 75 ms 24940 KB Output is correct
4 Correct 133 ms 26080 KB Output is correct
5 Correct 69 ms 22892 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 8556 KB Output is correct
2 Correct 26 ms 7660 KB Output is correct
3 Correct 15 ms 7532 KB Output is correct
4 Correct 16 ms 8044 KB Output is correct
5 Correct 18 ms 8300 KB Output is correct
6 Incorrect 36 ms 8300 KB Output isn't correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 13420 KB Output is correct
2 Correct 95 ms 13292 KB Output is correct
3 Correct 63 ms 9324 KB Output is correct
4 Correct 102 ms 13292 KB Output is correct
5 Correct 99 ms 13292 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 17900 KB Output is correct
2 Correct 144 ms 20648 KB Output is correct
3 Incorrect 149 ms 19948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 51 ms 7788 KB Output is correct
3 Correct 37 ms 6892 KB Output is correct
4 Correct 38 ms 6892 KB Output is correct
5 Correct 66 ms 17540 KB Output is correct
6 Correct 74 ms 15076 KB Output is correct
7 Correct 99 ms 18660 KB Output is correct
8 Correct 47 ms 7532 KB Output is correct
9 Correct 57 ms 7532 KB Output is correct
10 Correct 75 ms 24940 KB Output is correct
11 Correct 133 ms 26080 KB Output is correct
12 Correct 69 ms 22892 KB Output is correct
13 Correct 52 ms 8556 KB Output is correct
14 Correct 26 ms 7660 KB Output is correct
15 Correct 15 ms 7532 KB Output is correct
16 Correct 16 ms 8044 KB Output is correct
17 Correct 18 ms 8300 KB Output is correct
18 Incorrect 36 ms 8300 KB Output isn't correct