Submission #964250

# Submission time Handle Problem Language Result Execution time Memory
964250 2024-04-16T13:37:55 Z Ghetto Spring cleaning (CEOI20_cleaning) C++17
54 / 100
236 ms 69472 KB
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using pib = pair<int, bool>;
const int MAX_N = 1e5 + 5, MAX_Q = 1e5 + 5;;

int n, q;
vector<int> adj[MAX_N];
vector<int> upd[MAX_Q];

int root;
vector<int> child[MAX_N];
bool is_1[MAX_N];
void dfs1(int u, int par) {
    is_1[u] = (bool) (adj[u].size() == 1);
    for (int v : adj[u]) {
        if (v == par) continue;
        child[u].push_back(v);
        dfs1(v, u);
        if (is_1[v]) is_1[u] = !is_1[u];
    }
}
int n_1s[MAX_N], n_0s[MAX_N]; // From root to u
void dfs2(int u) {
    n_1s[u] += is_1[u], n_0s[u] += !is_1[u];
    for (int v : child[u]) {
        n_1s[v] += n_1s[u], n_0s[v] += n_0s[u];
        dfs2(v);
    }
}
int tot_n_1s, tot_n_0s;
void precomp1() {
    for (int i = 1; i <= n; i++) {
        if (adj[i].size() == 1) continue;
        root = i;
        dfs1(root, -1);
        break;
    }
    dfs2(root);
    for (int i = 1; i <= n; i++) 
        tot_n_1s += is_1[i], tot_n_0s += !is_1[i];     

    // for (int i = 1; i <= n; i++) {
    //     cout << i << ": " << n_1s[i] << " " << n_0s[i] << endl;
    // }
}

int new_child_size[MAX_N];
int n_leaves[MAX_Q];
int extra_n_1s[MAX_Q];
unordered_set<int> queries_w_flip1[MAX_N];
void precomp2(int query) {
    for (int u : upd[query]) {
        extra_n_1s[query]++;
        if (new_child_size[u]) {
            n_leaves[query]++;
            if (queries_w_flip1[u].count(query)) queries_w_flip1[u].erase(query);
            else queries_w_flip1[u].insert(query);
        }
        new_child_size[u]++;
    }
    for (int u : upd[query]) new_child_size[u]--;

    // cout << query << ": " << n_leaves[query] << " " << extra_n_1s[query] << endl;
}
void init() {
    for (int i = 1; i <= n; i++) new_child_size[i] = child[i].size();
    int tot_n_leaves = 0;
    for (int i = 1; i <= n; i++) tot_n_leaves += (bool) child[i].empty();
    for (int i = 1; i <= q; i++) n_leaves[i] = tot_n_leaves;
}

unordered_map<int, int> queries_w_flip2[MAX_N]; // {query, prev flipped}
vector<pii> flip_path[MAX_Q]; // {high, low (not incl.)}
void dfs3(int u) {
    unordered_map<int, bool> spec_queries; // {query, flip state}
    for (int query : queries_w_flip1[u]) queries_w_flip2[u][query] = u;

    for (int v : child[u]) {
        dfs3(v);

        if (queries_w_flip2[u].size() < queries_w_flip2[v].size()) queries_w_flip2[u].swap(queries_w_flip2[v]);
        for (pii el : queries_w_flip2[v]) {
            if (spec_queries.count(el.first)) {
                flip_path[el.first].push_back({el.second, u});
                spec_queries[el.first] = !spec_queries[el.first];
            } else {
                if (queries_w_flip2[u][el.first] == 0) queries_w_flip2[u][el.first] = el.second;
                else {
                    spec_queries[el.first] = false;
                    flip_path[el.first].push_back({el.second, u}); flip_path[el.first].push_back({queries_w_flip2[u][el.first], u});
                    queries_w_flip2[u].erase(el.first);
                }
            }
        }    
    }

    for (pib el : spec_queries) 
        if (el.second) queries_w_flip2[u][el.first] = u;
}
void precomp3() {
    dfs3(root);
    for (pii el : queries_w_flip2[root])
        flip_path[el.first].push_back({el.second, 0});

    // for (int i = 1; i <= q; i++) {
    //     cout << i << ": ";
    //     for (pii el : flip_path[i]) cout << el.first << "," << el.second << " ";
    //     cout << endl;
    // }
}

int main() {
    // freopen("spring.in", "r", stdin);

    cin >> n >> q; assert(n >= 3);
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= q; i++) {
        int s; cin >> s;
        for (int j = 1; j <= s; j++) {
            int u; cin >> u;
            upd[i].push_back(u);
        }
    }

    precomp1();
    init();
    for (int i = 1; i <= q; i++) precomp2(i);
    // for (int i = 1; i <= n; i++) {
    //     cout << i << " : ";
    //     for (int j : queries_w_flip1[i]) cout << j << " ";
    //     cout << endl;
    // }
    precomp3();

    for (int query = 1; query <= q; query++) {
        if (n_leaves[query] % 2 == 1) {
            cout << "-1" << '\n';
            continue;
        }

        int new_n_1s = tot_n_1s + extra_n_1s[query], new_n_0s = tot_n_0s;
        for (pii path : flip_path[query]) {
            int path_n_1s = n_1s[path.first] - n_1s[path.second], path_n_0s = n_0s[path.first] - n_0s[path.second];
            new_n_1s += path_n_0s - path_n_1s, new_n_0s += path_n_1s - path_n_0s;
        }

        int ans = new_n_1s + 2 * (new_n_0s - 1); assert(new_n_0s >= 1);
        cout << ans << '\n';
    }
}
# Verdict Execution time Memory Grader output
1 Correct 10 ms 21596 KB Output is correct
2 Incorrect 70 ms 32800 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 27 ms 22944 KB Output is correct
2 Correct 31 ms 23000 KB Output is correct
3 Correct 61 ms 26932 KB Output is correct
4 Correct 80 ms 31668 KB Output is correct
5 Correct 90 ms 33012 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 31 ms 23924 KB Output is correct
2 Correct 32 ms 23712 KB Output is correct
3 Correct 104 ms 49544 KB Output is correct
4 Correct 137 ms 60820 KB Output is correct
5 Correct 82 ms 46672 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 67 ms 28996 KB Output is correct
2 Incorrect 42 ms 25916 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 135 ms 47792 KB Output is correct
2 Correct 142 ms 40084 KB Output is correct
3 Correct 106 ms 35268 KB Output is correct
4 Correct 132 ms 40620 KB Output is correct
5 Correct 135 ms 40264 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 227 ms 57440 KB Output is correct
2 Correct 189 ms 58016 KB Output is correct
3 Correct 236 ms 69472 KB Output is correct
4 Correct 223 ms 68448 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 10 ms 21596 KB Output is correct
2 Incorrect 70 ms 32800 KB Output isn't correct
3 Halted 0 ms 0 KB -