K. Knights time limit per test2 seconds memory limit per test256 megabytes We all know…
- User
K. Knights time limit per test2 seconds memory limit per test256 megabytes We all know that the Middle Ages were a time of lords, vassals, and of course, knights. In this task, you need to solve a very important question: which of the N courtiers should become knights, the defenders of the kingdom.
For convenience, let's assign numbers to the courtiers from 1 to N . Each courtier, except for the king, is subordinate to exactly one courtier. The king is assigned the number one and does not obey anyone. For each courtier, the subordinate courtiers (vassals) are known, as well as two numbers L and R . These numbers imply that the retinue of this courtier must contain at least L and at most R knights. The retinue of a courtier includes all knights who are directly or indirectly subordinate to him, and of course, he himself if he is a knight.
More formally, a knight Y is subordinate to a courtier X if there exists a sequence a1,a2,…,aj such that a1 is subordinate to X , a2 is subordinate to a1 , and so on, with Y being subordinate to aj . It is guaranteed that it is possible to select knights in such a way that the specified condition is satisfied.
Input The first line of the input contains the number N (1≤N≤2⋅105 ) — the number of courtiers.
Each of the following N lines describes the i -th courtier: Li , Ri (the minimum and maximum size of the retinue), Ki (0≤Ki≤2⋅105,0≤L≤R≤109 ). After that, there are Ki numbers — the list of vassals of the i -th courtier (vassals can be numbered from 2 to N , different from i , and each number appears exactly once in the input file). It is guaranteed that an answer exists and each courtier is directly or indirectly subordinate to the king, who has the number 1 .
Output Print in the first line the number M (0≤M≤N ) — the number of knights. In the next line, print M distinct numbers (1≤Mi≤N ) — the numbers of the courtiers who should become knights. If there are multiple answers, you may print any.
Examples InputCopy 1 1 1 0 OutputCopy 1 1 InputCopy 5 2 2 2 2 3 0 2 2 4 5 0 0 0 1 1 0 0 1 0 OutputCopy 2 4 5 InputCopy 4 4 4 1 2 0 3 1 3 0 2 1 4 0 1 0 OutputCopy 4 1 2 3 4 Note In the first test, the king is forced to become a knight.
In the second test, courtiers 2 and 4 can become knights. Then the king and courtier 2 will have 2 knights in their retinue. Courtiers 3 and 5 will have no knights at all. Courtier 4 will have exactly 1 knight — himself.
In the third test, the king requires 4 knights, and thus all courtiers will have to become knights and join his retinue.
pleae give correct c++ code with all tests pass please.
- Assistant
To solve the problem of determining which courtiers should become knights while satisfying the constraints specified for each retinue, we can approach the problem in two main steps using dynamic programming on a tree structure:
-
First Pass (Post-order traversal):
- Compute the minimum and maximum number of knights that can exist in the subtree of each courtier.
- For each courtier, evaluate two scenarios: when the courtier is a knight and when the courtier is not a knight.
- Update the possible ranges of knights (
min_S_iandmax_S_i) based on the constraints[L_i, R_i].
-
Second Pass (Iterative traversal):
- Assign the number of knights for each subtree based on the previously computed ranges.
- Decide whether a courtier should be a knight or not based on the assigned number of knights for its subtree.
- Ensure that the constraints are satisfied when distributing the number of knights to the children.
C++ Implementation:
#include <bits/stdc++.h> using namespace std; typedef long long ll; // Structure to represent each node/courtier struct Node { int id; ll L; ll R; vector<int> children; ll min_S; ll max_S; bool can_be_knight; bool can_not_be_knight; }; int main(){ ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vector<Node> nodes(N+1); for(int i=1;i<=N;i++){ nodes[i].id = i; cin >> nodes[i].L >> nodes[i].R; int Ki; cin >> Ki; for(int j=0; j<Ki; j++){ int child; cin >> child; nodes[i].children.push_back(child); } } // First pass: Post-order traversal to compute min_S and max_S // Implemented iteratively // Using a stack of pairs: (node_id, processed_flag) stack<pair<int, bool>> stk; stk.emplace(1, false); while(!stk.empty()){ auto [node_id, processed] = stk.top(); stk.pop(); if(!processed){ stk.emplace(node_id, true); for(auto &child : nodes[node_id].children){ stk.emplace(child, false); } } else{ Node &node = nodes[node_id]; if(node.children.empty()){ // Leaf node // possible_not_knight_S: [0,0] intersect [L, R] bool not_knight_possible = (node.L <= 0 && 0 <= node.R); // possible_knight_S: [1,1] intersect [L, R] bool knight_possible = (node.L <= 1 && 1 <= node.R); node.can_not_be_knight = not_knight_possible; node.can_be_knight = knight_possible; vector<ll> possible_S; if(not_knight_possible){ possible_S.push_back(0); } if(knight_possible){ possible_S.push_back(1); } if(possible_S.empty()){ // Should not happen as per problem statement } node.min_S = *min_element(possible_S.begin(), possible_S.end()); node.max_S = *max_element(possible_S.begin(), possible_S.end()); } else{ // Non-leaf node ll sum_min = 0, sum_max = 0; for(auto &child : node.children){ sum_min += nodes[child].min_S; sum_max += nodes[child].max_S; } // possible_not_knight_S: [sum_min, sum_max] intersect [L, R] ll not_knight_low = max(node.L, sum_min); ll not_knight_high = min(node.R, sum_max); bool can_not_knight = (not_knight_low <= not_knight_high); // possible_knight_S: [1 + sum_min, 1 + sum_max] intersect [L, R] ll knight_low = max(node.L, sum_min + 1); ll knight_high = min(node.R, sum_max + 1); bool can_knight = (knight_low <= knight_high); node.can_not_be_knight = can_not_knight; node.can_be_knight = can_knight; vector<ll> possible_S; if(can_not_knight){ possible_S.push_back(not_knight_low); possible_S.push_back(not_knight_high); } if(can_knight){ possible_S.push_back(knight_low); possible_S.push_back(knight_high); } if(possible_S.empty()){ // Should not happen as per problem statement } node.min_S = *min_element(possible_S.begin(), possible_S.end()); node.max_S = *max_element(possible_S.begin(), possible_S.end()); } } } // Second pass: Assign sums and determine knights vector<int> knights; // Stack for iterative assignment: pair of (node_id, desired_S_i) // We'll use a stack of pairs stack<pair<int, ll>> assign_stack; // Choose root's desired_S_i as its min_S assign_stack.emplace(1, nodes[1].min_S); while(!assign_stack.empty()){ auto [node_id, desired_S_i] = assign_stack.top(); assign_stack.pop(); Node &node = nodes[node_id]; // Calculate sum_children_min and sum_children_max ll sum_children_min = 0, sum_children_max = 0; for(auto &child : node.children){ sum_children_min += nodes[child].min_S; sum_children_max += nodes[child].max_S; } // Check if node can be knight or not bool can_knight = false, can_not_knight = false; if(node.can_be_knight && (desired_S_i >= (sum_children_min + 1)) && (desired_S_i <= (sum_children_max +1))){ can_knight = true; } if(node.can_not_be_knight && (desired_S_i >= sum_children_min) && (desired_S_i <= sum_children_max)){ can_not_knight = true; } // Decide to mark as knight or not bool mark_knight = false; ll desired_sum_children; if(can_not_knight){ // Prefer not being knight mark_knight = false; desired_sum_children = desired_S_i; } else{ // Must be knight mark_knight = true; desired_sum_children = desired_S_i -1; knights.push_back(node_id); } // Assign sums to children if(!node.children.empty()){ ll total_min = 0; for(auto &child : node.children){ total_min += nodes[child].min_S; } ll remaining = desired_sum_children - total_min; // Assign extra to children // To ensure we distribute the remaining appropriately, iterate in order // and assign as much as possible to each child vector<pair<int, ll>> assign_children; for(auto &child : node.children){ if(remaining > 0){ ll extra = min(nodes[child].max_S - nodes[child].min_S, remaining); ll assigned_S = nodes[child].min_S + extra; assign_children.emplace_back(child, assigned_S); remaining -= extra; } else{ ll assigned_S = nodes[child].min_S; assign_children.emplace_back(child, assigned_S); } } // Push children to stack in reverse order to maintain left-to-right processing for(int i = assign_children.size() -1; i >=0; i--){ assign_stack.emplace(assign_children[i].first, assign_children[i].second); } } } // Now, output the list of knights // Sort the knights for output sort(knights.begin(), knights.end()); cout << knights.size() << "\n"; for(auto &id : knights){ cout << id << " "; } cout << "\n"; } -