Submission #290095

#	Time	Username	Problem	Language	Result	Execution time	Memory
290095		model_code	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	416 ms	29948 KiB

cleaning

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

//
// Solution to task Spring-cleaning by Zsolt Németh @birka0
//
// Use dfs to compute: node depths, subtree leaf count,
// 		even subtree leaf count on the path to root for all nodes,
//		the cost of cleaning the tree without adding any leafs.
// Preread the whole input and for each node store the question_id-s for which new leaves were attached to it.
// Run a second dfs and dynamically maintain (in a bottom-up DP manner) the unpaired extra leaves in each subtree: 
// 		the question_id-s are unique for each, and their parent nodes must be stored.
// For each internal node, merge these collections of question id-s for all its children 
//		(insert the smaller into the bigger to maintain low complexity).
// Whenever we encounter the same question_id twice, we can pair and remove them (as we are in their LCA node).
// Store the cleaning cost changes in a vector for each question separately.
//

int N,Q,D, root=1, dep[100001], leafcnt[100001], even_to_root[100001];
int x,y;
int base_ans, mod_ans[100001];
vector<int> e[100001], q_adds[100001];
map<int,int> collect[100001];

int calc_change(int deep_node, int ancestor_node) {
    return dep[deep_node]-dep[ancestor_node] - 2*(even_to_root[deep_node]-even_to_root[ancestor_node]);
}

void dfs(int node, int par, int depth = 0) {
    dep[node] = depth;
    if (e[node].size()==1) {
        leafcnt[node] = 1;
        return;
    }
    for (int ch : e[node]) {
        if (ch == par) continue;
        dfs(ch, node, depth+1);
        leafcnt[node] += leafcnt[ch];
    }
    if (leafcnt[node] % 2 == 0) ++base_ans;
}
int dfs2(int node, int par) {
    even_to_root[node] = even_to_root[par] + (leafcnt[node]%2 == 0);
    if (e[node].size() == 1) {
        for (int k=0; k < q_adds[node].size(); ++k) {
            int cnt = 1;
            while (k+1 < q_adds[node].size() && q_adds[node][k]==q_adds[node][k+1]) ++k, ++cnt;
            if (cnt%2 == 0) collect[node][q_adds[node][k]] = node;
        }
        return node;
    }
    int coll_id = 0;
    for (int ch : e[node]) {
        if (ch == par) continue;
        int ret_coll = dfs2(ch, node);
        if (coll_id == 0) coll_id = ret_coll;
        else {
            if (collect[coll_id].size() < collect[ret_coll].size()) swap(coll_id, ret_coll);
            for (auto& qq : collect[ret_coll]) {
                if (collect[coll_id].count(qq.first)) {
                    int foundnode = collect[coll_id][qq.first];
                    collect[coll_id].erase(qq.first);
                    mod_ans[qq.first] += calc_change(qq.second, node) + calc_change(foundnode, node);
                }
                else collect[coll_id].insert(qq);
            }
        }
    }
    for (int k=0; k < q_adds[node].size(); ++k) {
        int cnt = 1;
        while (k+1 < q_adds[node].size() && q_adds[node][k]==q_adds[node][k+1]) ++k, ++cnt;
        if (cnt%2 == 1) {
            if (collect[coll_id].count(q_adds[node][k])) {
                const auto& qq = collect[coll_id].find(q_adds[node][k]);
                mod_ans[qq->first] += calc_change(qq->second, node);
                collect[coll_id].erase(qq);
            }
            else collect[coll_id][q_adds[node][k]] = node;
        }
    }
    return coll_id;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> N >> Q;
    for (int i=1; i<N; ++i) {
        cin >> x >> y;
        e[x].push_back(y), e[y].push_back(x);
    }
    while (e[root].size() == 1) ++root;
    base_ans = N-1;
    dfs(root, 0);
    for (int q=1; q<=Q; ++q) {
        cin >> D;
        mod_ans[q] = D;
        for (int i=0; i<D; ++i) {
            cin >> x;
            q_adds[x].push_back(q);
        }
    }
    int root_coll = dfs2(root, 0);
    for (int q=1; q<=Q; ++q) {
        const auto& qq = collect[root_coll].find(q);
        if (leafcnt[root]%2 == 0 && qq==collect[root_coll].end()) cout << base_ans+mod_ans[q]-1 << endl;
        else if (leafcnt[root]%2 == 1 && qq!=collect[root_coll].end()) cout << base_ans+mod_ans[q]+calc_change(qq->second,root) << endl;
        else cout << -1 << endl;
    }
    return 0;
}

Compilation message (stderr)

cleaning.cpp: In function 'int dfs2(int, int)':
cleaning.cpp:49:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int k=0; k < q_adds[node].size(); ++k) {
      |                       ~~^~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:51:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             while (k+1 < q_adds[node].size() && q_adds[node][k]==q_adds[node][k+1]) ++k, ++cnt;
      |                    ~~~~^~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int k=0; k < q_adds[node].size(); ++k) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         while (k+1 < q_adds[node].size() && q_adds[node][k]==q_adds[node][k+1]) ++k, ++cnt;
      |                ~~~~^~~~~~~~~~~~~~~~~~~~~

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