제출 #1055175

#제출 시각아이디문제언어결과실행 시간메모리
1055175kiryl_krutskoSpring cleaning (CEOI20_cleaning)C++14
0 / 100
1031 ms17492 KiB
#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; } } }

컴파일 시 표준 에러 (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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...