제출 #964260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964260		Ghetto	Spring cleaning (CEOI20_cleaning)	C++17	9 / 100	1038 ms	55772 KiB

cleaning

#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 check(int query) {
    int ones = extra_n_1s[query], zeros = 1;
    for (int u : upd[query]) 
        new_child_size[u]++;
    for (int u = 2; u <= n; u++)
        ones += (bool) (new_child_size[u] % 2 == 1 || new_child_size[u] == 0), zeros += (bool) (new_child_size[u] % 2 == 0 && new_child_size[u] != 0);
    for (int u : upd[query]) 
        new_child_size[u]--;

    return ones + 2 * (zeros - 1);
}

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);
        int ans = check(query);
        cout << ans << '\n';
    }
}

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