This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
using namespace std;
int root_num = 0;
struct cost {
int value;
int q_num;
cost(int v, int q) {
value = v;
q_num = q;
}
};
struct node {
int num = -2;
vector<node*> conns;
vector<cost> costs;
};
int check_subtree(node* root, int parent_num) {
int ans = 0;
int odd_children_num = 0;
for (int i = 0; i < root->conns.size(); i++) {
node* child = root->conns[i];
if (child->num == parent_num) {
root->conns.insert(root->conns.begin(), child);
root->conns.erase(root->conns.begin() + i + 1);
continue;
}
int child_cost = check_subtree(child, root->num);
if (child_cost >= 0) {
ans += (child_cost + 1);
odd_children_num++;
}
else ans += (2 - child_cost);
}
if (odd_children_num % 2 == 0) ans = -ans;
root->costs.push_back(cost(ans, 0));
return ans;
}
int find_answer(node* root) {
if (root->conns.size() == 1) {
if (root->conns[0]->conns.size() == 1) return 1;
else {
root_num = root->conns[0]->num;
return find_answer(root->conns[0]);
}
}
int total_cost = check_subtree(root, -1);
if (total_cost < 0) return -total_cost;
else return -1;
}
void update_ancestors_costs(node* cur, int changed_child_init_cost, int changed_child_new_cost, int q_num) {
int cur_old_cost;
if (cur->costs[0].q_num == q_num) cur_old_cost = cur->costs[0].value;
else cur_old_cost = cur->costs[cur->costs.size() - 1].value;
int cur_new_cost = abs(cur_old_cost) + abs(abs(changed_child_new_cost) - abs(changed_child_init_cost));
if (changed_child_init_cost < 0) cur_new_cost--;
if (changed_child_new_cost < 0) cur_new_cost++;
if (changed_child_init_cost * changed_child_new_cost <= 0) {
cur_new_cost = -cur_new_cost;
}
cur->costs.insert(cur->costs.begin(), cost(cur_new_cost, q_num));
if (cur->costs.size() > 2) cur->costs.erase(cur->costs.begin() + 1);
if (cur->num != root_num) update_ancestors_costs(cur->conns[0], cur_old_cost, cur_new_cost, q_num);
}
int main()
{
int n, q;
cin >> n >> q;
vector<node> vec(n);
int a, b;
vec[0].num = 0;
int leaves_num = n;
int ans;
for (int i = 1; i < n; i++) {
vec[i].num = i;
cin >> a >> b;
a--; b--;
vec[a].conns.push_back(&vec[b]);
vec[b].conns.push_back(&vec[a]);
if (vec[a].conns.size() == 2) leaves_num--;
if (vec[b].conns.size() == 2) leaves_num--;
}
ans = find_answer(&vec[0]);
int new_num;
for (int i = 0; i < q; i++) {
int new_leaves_num = 0;
cin >> new_num;
for (int j = 0; j < new_num; j++) {
cin >> a; a--;
int init_cost = vec[a].costs[vec[a].costs.size() - 1].value;
if (init_cost <= 0) {
vec[a].costs.insert(vec[a].costs.begin(), cost(abs(init_cost) + 1, i));
}
else {
vec[a].costs.insert(vec[a].costs.begin(), cost(-(init_cost + 1), i) );
}
if (vec[a].costs.size() > 2) vec[a].costs.erase(vec[a].costs.begin() + 1);
if (a != root_num) update_ancestors_costs(vec[a].conns[0], init_cost, vec[a].costs[0].value, i);
if (vec[a].conns.size() != 1)
new_leaves_num++;
}
if ((leaves_num + new_leaves_num) % 2 == 1) cout << -1 << endl;
else {
cout << -vec[root_num].costs[0].value << endl;
}
}
}
Compilation message (stderr)
cleaning.cpp: In function 'int check_subtree(node*, int)':
cleaning.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for (int i = 0; i < root->conns.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:83:6: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
83 | int ans;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |