Submission #1055175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055175		kiryl_krutsko	Spring cleaning (CEOI20_cleaning)	C++14	0 / 100	1031 ms	17492 KiB

cleaning

#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;
      |      ^~~

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