oj.uz

Submission #290095

# Submission time Handle Problem Language Result Execution time Memory
290095 2020-09-03T12:04:43 Z model_code Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 416 ms 29948 KB 
#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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 77 ms 15992 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10496 KB Output is correct
2 Correct 17 ms 10496 KB Output is correct
3 Correct 51 ms 14660 KB Output is correct
4 Correct 59 ms 15088 KB Output is correct
5 Correct 83 ms 16752 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 11264 KB Output is correct
2 Correct 21 ms 11264 KB Output is correct
3 Correct 79 ms 28028 KB Output is correct
4 Correct 97 ms 28024 KB Output is correct
5 Correct 70 ms 26232 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 13816 KB Output is correct
2 Correct 30 ms 12280 KB Output is correct
3 Correct 17 ms 10624 KB Output is correct
4 Correct 18 ms 11904 KB Output is correct
5 Correct 21 ms 12032 KB Output is correct
6 Correct 39 ms 12920 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 26744 KB Output is correct
2 Correct 131 ms 20856 KB Output is correct
3 Correct 91 ms 18040 KB Output is correct
4 Correct 135 ms 21704 KB Output is correct
5 Correct 130 ms 21112 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 29948 KB Output is correct
2 Correct 381 ms 26104 KB Output is correct
3 Correct 405 ms 29688 KB Output is correct
4 Correct 408 ms 29048 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 77 ms 15992 KB Output is correct
3 Correct 18 ms 10496 KB Output is correct
4 Correct 17 ms 10496 KB Output is correct
5 Correct 51 ms 14660 KB Output is correct
6 Correct 59 ms 15088 KB Output is correct
7 Correct 83 ms 16752 KB Output is correct
8 Correct 20 ms 11264 KB Output is correct
9 Correct 21 ms 11264 KB Output is correct
10 Correct 79 ms 28028 KB Output is correct
11 Correct 97 ms 28024 KB Output is correct
12 Correct 70 ms 26232 KB Output is correct
13 Correct 42 ms 13816 KB Output is correct
14 Correct 30 ms 12280 KB Output is correct
15 Correct 17 ms 10624 KB Output is correct
16 Correct 18 ms 11904 KB Output is correct
17 Correct 21 ms 12032 KB Output is correct
18 Correct 39 ms 12920 KB Output is correct
19 Correct 277 ms 26744 KB Output is correct
20 Correct 131 ms 20856 KB Output is correct
21 Correct 91 ms 18040 KB Output is correct
22 Correct 135 ms 21704 KB Output is correct
23 Correct 130 ms 21112 KB Output is correct
24 Correct 416 ms 29948 KB Output is correct
25 Correct 381 ms 26104 KB Output is correct
26 Correct 405 ms 29688 KB Output is correct
27 Correct 408 ms 29048 KB Output is correct
28 Correct 116 ms 18860 KB Output is correct
29 Correct 126 ms 22064 KB Output is correct
30 Correct 77 ms 16748 KB Output is correct
31 Correct 97 ms 28048 KB Output is correct
32 Correct 130 ms 20816 KB Output is correct
33 Correct 132 ms 20984 KB Output is correct
34 Correct 161 ms 23552 KB Output is correct
35 Correct 166 ms 23160 KB Output is correct