#include <bits/stdc++.h> using namespace std; typedef long long ll; // Fast IO setup…
- User
#include <bits/stdc++.h> using namespace std;
typedef long long ll;
// Fast IO setup struct FastIO { FastIO() { ios::sync_with_stdio(false); cin.tie(nullptr); } };
// Subtask 1: n, q, sum of k <= 1000 void solve_subtask1(int n, int q, const vector& parents, vector country, const vector& c, const vector<pair<int, vector>>& queries) { // Build tree vector<vector> adj(n + 1, vector()); for(int i = 2; i <= n; ++i){ adj[parents[i-2]].push_back(i); }
// Build country lists vector<vector<int>> countries(n + 1, vector<int>()); for(int i = 1; i <= n; ++i){ countries[country[i]].push_back(i); } // Process queries for(auto &[type, params] : queries){ if(type == 1){ int v = params[0]; int tnew = params[1]; int told = country[v]; // Remove v from old country auto &vec_old = countries[told]; vec_old.erase(find(vec_old.begin(), vec_old.end(), v)); // Add v to new country countries[tnew].push_back(v); // Update country country[v] = tnew; } else{ int t = params[0]; int k = params[1]; vector<int> treasures(params.begin() + 2, params.end()); // Mark treasures vector<bool> is_treasure(n + 1, false); for(auto x: treasures) is_treasure[x] = true; // Compute numv using DFS vector<long long> numv(n + 1, 0); // Recursive DFS function<long long(int)> dfs = [&](int u) -> long long{ long long cnt = is_treasure[u] ? 1 : 0; for(auto &v_child: adj[u]){ cnt += dfs(v_child); } numv[u] = cnt; return cnt; }; dfs(1); // Now iterate over country t long long max_tax = 0; for(auto v: countries[t]){ long long tax = c[v] * numv[v]; if(tax > max_tax) max_tax = tax; } cout << max_tax << "\n"; } }}
// Subtask 2: No type 1 queries and ti = 1 void solve_subtask2(int n, int q, const vector& parents, const vector& country, const vector& c, const vector<pair<int, vector>>& queries) { // Since all countries are 1 and no type 1 queries // Preprocess parent array vector parent(n + 1, 0); for(int i = 2; i <= n; ++i){ parent[i] = parents[i-2]; }
// Initialize variables for queries vector<int> last_visit(n + 1, 0); vector<int> cnt_v(n + 1, 0); int current_query_id = 0; for(auto &[type, params] : queries){ if(type == 1){ // No type1 queries in subtask2 continue; } else{ // Type 2 query int t = params[0]; // Always 1 int k = params[1]; vector<int> treasures(params.begin() + 2, params.end()); current_query_id++; ll max_tax = 0; for(auto a_i: treasures){ int v = a_i; while(v != 0){ if(last_visit[v] != current_query_id){ cnt_v[v] = 0; last_visit[v] = current_query_id; } cnt_v[v] +=1; ll current_tax = c[v] * (ll)cnt_v[v]; if(current_tax > max_tax){ max_tax = current_tax; } v = parent[v]; } } cout << max_tax << "\n"; } }}
// Subtask 3: No type 1 queries void solve_subtask3(int n, int q, const vector& parents, const vector& country, const vector& c, const vector<pair<int, vector>>& queries) { // Precompute in and out times using Euler Tour // Build tree vector<vector> adj(n + 1, vector()); for(int i = 2; i <= n; ++i){ adj[parents[i-2]].push_back(i); }
// Euler Tour vector<int> in_order(n + 1), out_order(n + 1); int timer = 1; // Iterative DFS stack<pair<int, int>> stk; stk.emplace(1, 0); // node, state while(!stk.empty()){ auto [u, state] = stk.top(); stk.pop(); if(state == 0){ in_order[u] = timer; timer++; stk.emplace(u, 1); for(auto it = adj[u].rbegin(); it != adj[u].rend(); ++it){ stk.emplace(*it, 0); } } else{ out_order[u] = timer -1; } } // Build country lists vector<vector<int>> countries(n + 1, vector<int>()); for(int i = 1; i <= n; ++i){ countries[country[i]].push_back(i); } // Sort each country's nodes by c_v descendingly for(int t = 1; t <= n; ++t){ if(!countries[t].empty()){ sort(countries[t].begin(), countries[t].end(), [&](const int a, const int b) -> bool{ if(c[a] != c[b]) return c[a] > c[b]; return in_order[a] < in_order[b]; }); } } // BIT implementation vector<int> BIT_tree(n + 2, 0); auto update = [&](auto &update_ref, int idx, int delta) -> void{ while(idx <= n){ BIT_tree[idx] += delta; idx += idx & -idx; } }; auto query = [&](auto &query_ref, int idx) -> int{ int res = 0; while(idx > 0){ res += BIT_tree[idx]; idx -= idx & -idx; } return res; }; // Process queries for(auto &[type, params] : queries){ if(type == 1){ // No type1 queries in subtask3 continue; } else{ // Type2 query int t = params[0]; int k = params[1]; vector<int> treasures(params.begin() + 2, params.end()); // Insert treasures into BIT for(auto &x: treasures){ update(update, in_order[x], 1); } // Iterate through t's nodes sorted by c_v descendingly ll max_tax = 0; for(auto &v: countries[t]){ // Calculate number of treasures in subtree of v int cnt = query(query, out_order[v]) - query(query, in_order[v]-1); ll tax = (ll)c[v] * cnt; if(tax > max_tax){ max_tax = tax; } } cout << max_tax << "\n"; // Remove treasures from BIT for(auto &x: treasures){ update(update, in_order[x], -1); } } }}
// Subtask 4: pi = i -1 (tree is a path) void solve_subtask4(int n, int q, const vector& parents, vector country, const vector& c, const vector<pair<int, vector>>& queries) { // Since the tree is a path: 1-2-3-...-n // In this tree, in_order is simply the node number // No need for Euler Tour
// Build country lists, sorted vector<vector<int>> countries(n + 1, vector<int>()); for(int i = 1; i <= n; ++i){ countries[country[i]].push_back(i); } for(int t = 1; t <= n; ++t){ if(!countries[t].empty()){ sort(countries[t].begin(), countries[t].end()); } } for(auto &[type, params] : queries){ if(type == 1){ // Type1 query: Change country assignment int v = params[0]; int tnew = params[1]; int told = country[v]; if(told != tnew){ // Remove v from old country auto &vec_old = countries[told]; int pos = lower_bound(vec_old.begin(), vec_old.end(), v) - vec_old.begin(); if(pos < vec_old.size() && vec_old[pos] == v){ vec_old.erase(vec_old.begin() + pos); } // Add v to new country auto &vec_new = countries[tnew]; vec_new.insert(lower_bound(vec_new.begin(), vec_new.end(), v), v); // Update country assignment country[v] = tnew; } } else{ // Type2 query: Compute maximum tax int t = params[0]; int k = params[1]; vector<int> treasures(params.begin() + 2, params.end()); sort(treasures.begin(), treasures.end()); const vector<int> &nodes = countries[t]; if(nodes.empty()){ cout << "0\n"; continue; } ll max_tax = 0; for(auto v: nodes){ // In a path tree, subtree of v includes nodes v to n // Number of treasures >= v int numv = treasures.end() - lower_bound(treasures.begin(), treasures.end(), v); if(numv > 0){ ll tax = c[v] * (ll)numv; if(tax > max_tax){ max_tax = tax; } } } cout << max_tax << "\n"; } }}
// Subtask 5: pi = floor(i/2) (binary tree), with type 1 queries void solve_subtask5(int n, int q, const vector& parents, vector country, const vector& c, const vector<pair<int, vector>>& queries) { // Build tree vector<vector> adj(n + 1, vector()); for(int i = 2; i <= n; ++i){ adj[parents[i-2]].push_back(i); }
// Euler Tour vector<int> in_order(n + 1), out_order(n + 1); int timer = 1; // Iterative DFS stack<pair<int, int>> stk; stk.emplace(1, 0); // node, state while(!stk.empty()){ auto [u, state] = stk.top(); stk.pop(); if(state == 0){ in_order[u] = timer; timer++; stk.emplace(u, 1); for(auto it = adj[u].rbegin(); it != adj[u].rend(); ++it){ stk.emplace(*it, 0); } } else{ out_order[u] = timer -1; } } // Initialize countries: vector of vectors, sorted by in_order vector<vector<int>> countries(n + 1, vector<int>()); for(int i = 1; i <= n; ++i){ countries[country[i]].push_back(i); } // Sort each country's nodes by in_order for(int t = 1; t <= n; ++t){ if(!countries[t].empty()){ sort(countries[t].begin(), countries[t].end(), [&](const int a, const int b) -> bool{ return in_order[a] < in_order[b]; }); } } // To handle dynamic updates, use a BIT for treasures vector<int> BIT_tree(n + 2, 0); auto update_BIT = [&](auto &update_ref, int idx, int delta) -> void{ while(idx <= n){ BIT_tree[idx] += delta; idx += idx & -idx; } }; auto query_BIT = [&](auto &query_ref, int idx) -> int{ int res = 0; while(idx > 0){ res += BIT_tree[idx]; idx -= idx & -idx; } return res; }; // Process queries for(auto &[type, params] : queries){ if(type == 1){ // Type1 query: Change country assignment int v = params[0]; int tnew = params[1]; int told = country[v]; if(told != tnew){ // Remove v from old country auto &vec_old = countries[told]; // Binary search to find v based on in_order int pos = lower_bound(vec_old.begin(), vec_old.end(), v, [&](const int a, const int b) -> bool{ return in_order[a] < in_order[b]; }) - vec_old.begin(); // Ensure correct node while(pos < vec_old.size() && in_order[vec_old[pos]] == in_order[v] && vec_old[pos] != v){ pos++; } if(pos < vec_old.size() && vec_old[pos] == v){ vec_old.erase(vec_old.begin() + pos); } // Insert v into new country auto &vec_new = countries[tnew]; int insert_pos = lower_bound(vec_new.begin(), vec_new.end(), v, [&](const int a, const int b) -> bool{ return in_order[a] < in_order[b]; }) - vec_new.begin(); vec_new.insert(vec_new.begin() + insert_pos, v); // Update country assignment country[v] = tnew; } } else{ // Type2 query: Compute maximum tax int t = params[0]; int k = params[1]; vector<int> treasures(params.begin() + 2, params.end()); // Insert treasures into BIT for(auto &x: treasures){ update_BIT(update_BIT, in_order[x], 1); } // Iterate through t's nodes sorted by in_order ll max_tax = 0; for(auto &v: countries[t]){ // Calculate number of treasures in subtree of v int cnt = query_BIT(query_BIT, out_order[v]) - query_BIT(query_BIT, in_order[v]-1); ll tax = (ll)c[v] * cnt; if(tax > max_tax){ max_tax = tax; } } cout << max_tax << "\n"; // Remove treasures from BIT for(auto &x: treasures){ update_BIT(update_BIT, in_order[x], -1); } } }}
int main(){ FastIO fio;
int n, q; cin >> n >> q; // Read parents for the tree vector<int> parents(n-1); for(auto &p: parents) cin >> p; // Read initial country assignments vector<int> country(n +1); for(int i =1; i <=n; ++i) cin >> country[i]; // Read c values vector<long long> c(n +1); for(int i =1; i <=n; ++i) cin >> c[i]; // Read all queries // Each query is a pair: type and parameters // For type 1: [v, tnew] // For type 2: [t, k, a1, a2, ..., ak] vector<pair<int, vector<int>>> queries; queries.reserve(q); for(int i =0; i < q; ++i){ int xi; cin >> xi; if(xi == 1){ int v, tnew; cin >> v >> tnew; queries.emplace_back(make_pair(xi, vector<int>{v, tnew})); } else{ int t, k; cin >> t >> k; vector<int> params = {t, k}; params.reserve(k +2); for(int j =0; j < k; ++j){ int a; cin >> a; params.push_back(a); } queries.emplace_back(make_pair(xi, params)); } } // Determine which subtask to solve based on constraints // For demonstration, we'll assume all subtasks are independent // and call each solve function separately with relevant constraints // In practice, you'd implement a single solution handling all constraints // Example calls (uncomment the one relevant to your subtask) // solve_subtask1(n, q, parents, country, c, queries); // solve_subtask2(n, q, parents, country, c, queries); // solve_subtask3(n, q, parents, country, c, queries); // solve_subtask4(n, q, parents, country, c, queries); solve_subtask5(n, q, parents, country, c, queries); return 0;}
Subtask 1: n, q and sum of all ki <= 1000. Subtask 2: No query type 1 and ti = 1. Subtask 3: No query type 1. Subtask 4: pi = i - 1. Subtask 5:pi = ⌊ i/2 ⌋ the ⌊ ⌋ is round down. please help me call each function
- Assistant
Certainly! It seems you're trying to call the appropriate
solve_subtaskXfunction based on the constraints specified for each subtask. Here's how you can modify yourmain()function to automatically determine which subtask to solve and call the corresponding function:First, you'll need to calculate certain conditions based on the input to determine which subtask applies. Here's how you can do it step by step.
Step 1: Initialize variables to track conditions
You'll need variables to check for the following conditions:
sum_k: Sum of allkvalues in the queries (for Subtask 1).has_type1_query: Whether there is any type 1 query (for Subtasks 2 and 3).all_ti_equal1: Whether allt_iin the queries are equal to1(for Subtask 2).pi_equal_i_minus1: Whetherp_i = i - 1for alli(for Subtask 4).pi_equal_floor_i_div_2: Whetherp_i = ⌊i/2⌋for alli(for Subtask 5).
Step 2: Read the input and update these variables accordingly
Here's how you can do it:
int n, q; cin >> n >> q; // Read parents for the tree vector<int> parents(n-1); bool pi_equal_i_minus1 = true; bool pi_equal_floor_i_div_2 = true; for(int i = 2; i <= n; ++i){ cin >> parents[i-2]; int pi = parents[i-2]; if(pi != i -1) pi_equal_i_minus1 = false; if(pi != i / 2) pi_equal_floor_i_div_2 = false; } // Read initial country assignments vector<int> country(n +1); for(int i =1; i <=n; ++i) cin >> country[i]; // Read c values vector<long long> c(n +1); for(int i =1; i <=n; ++i) cin >> c[i]; // Read all queries // Each query is a pair: type and parameters // For type 1: [v, tnew] // For type 2: [t, k, a1, a2, ..., ak] vector<pair<int, vector<int>>> queries; queries.reserve(q); int sum_k = 0; bool has_type1_query = false; bool all_ti_equal1 = true; for(int i =0; i < q; ++i){ int xi; cin >> xi; if(xi == 1){ int v, tnew; cin >> v >> tnew; queries.emplace_back(make_pair(xi, vector<int>{v, tnew})); has_type1_query = true; } else{ int t, k; cin >> t >> k; vector<int> params = {t, k}; params.reserve(k +2); sum_k += k; if(t != 1) all_ti_equal1 = false; for(int j =0; j < k; ++j){ int a; cin >> a; params.push_back(a); } queries.emplace_back(make_pair(xi, params)); } }Step 3: Determine which subtask applies and call the appropriate function
Now, implement the logic to decide which subtask's solution should be executed:
if(n <= 1000 && q <= 1000 && sum_k <= 1000){ // Subtask 1 conditions met solve_subtask1(n, q, parents, country, c, queries); } else if(pi_equal_i_minus1){ // Subtask 4 conditions met solve_subtask4(n, q, parents, country, c, queries); } else if(pi_equal_floor_i_div_2){ // Subtask 5 conditions met solve_subtask5(n, q, parents, country, c, queries); } else if(!has_type1_query && all_ti_equal1){ // Subtask 2 conditions met solve_subtask2(n, q, parents, country, c, queries); } else if(!has_type1_query){ // Subtask 3 conditions met solve_subtask3(n, q, parents, country, c, queries); } else{ // No solution available for the general case cerr << "No solution available for the given constraints\n"; }Final Combined
main()FunctionPutting it all together, here's your updated
main()function:int main(){ FastIO fio; int n, q; cin >> n >> q; // Read parents for the tree vector<int> parents(n-1); bool pi_equal_i_minus1 = true; bool pi_equal_floor_i_div_2 = true; for(int i = 2; i <= n; ++i){ cin >> parents[i-2]; int pi = parents[i-2]; if(pi != i -1) pi_equal_i_minus1 = false; if(pi != i / 2) pi_equal_floor_i_div_2 = false; } // Read initial country assignments vector<int> country(n +1); for(int i =1; i <=n; ++i) cin >> country[i]; // Read c values vector<long long> c(n +1); for(int i =1; i <=n; ++i) cin >> c[i]; // Read all queries // Each query is a pair: type and parameters // For type 1: [v, tnew] // For type 2: [t, k, a1, a2, ..., ak] vector<pair<int, vector<int>>> queries; queries.reserve(q); int sum_k = 0; bool has_type1_query = false; bool all_ti_equal1 = true; for(int i =0; i < q; ++i){ int xi; cin >> xi; if(xi == 1){ int v, tnew; cin >> v >> tnew; queries.emplace_back(make_pair(xi, vector<int>{v, tnew})); has_type1_query = true; } else{ int t, k; cin >> t >> k; vector<int> params = {t, k}; params.reserve(k +2); sum_k += k; if(t != 1) all_ti_equal1 = false; for(int j =0; j < k; ++j){ int a; cin >> a; params.push_back(a); } queries.emplace_back(make_pair(xi, params)); } } // Determine which subtask to solve based on constraints if(n <= 1000 && q <= 1000 && sum_k <= 1000){ // Subtask 1 conditions met solve_subtask1(n, q, parents, country, c, queries); } else if(pi_equal_i_minus1){ // Subtask 4 conditions met solve_subtask4(n, q, parents, country, c, queries); } else if(pi_equal_floor_i_div_2){ // Subtask 5 conditions met solve_subtask5(n, q, parents, country, c, queries); } else if(!has_type1_query && all_ti_equal1){ // Subtask 2 conditions met solve_subtask2(n, q, parents, country, c, queries); } else if(!has_type1_query){ // Subtask 3 conditions met solve_subtask3(n, q, parents, country, c, queries); } else{ // No solution available for the general case cerr << "No solution available for the given constraints\n"; } return 0; }With this setup, your program will automatically determine which subtask's solution is applicable based on the input provided and then execute the corresponding function.
Explanation of the Logic
- Subtask 1: Checks if
n,q, andsum_kare all less than or equal to1000. If so, it callssolve_subtask1. - Subtask 4: If
p_i = i - 1for alli(i.e., the tree is a path like1-2-3-...-n), it callssolve_subtask4. - Subtask 5: If
p_i = ⌊i/2⌋for alli, it callssolve_subtask5. - Subtask 2: If there are no type 1 queries and all
t_i = 1, it callssolve_subtask2. - Subtask 3: If there are no type 1 queries (but
t_imay not be1), it callssolve_subtask3. - If none of the above conditions are met, the program outputs an error message indicating no solution is available.
Note: Ensure that each
solve_subtaskXfunction is correctly implemented to handle the specific conditions of the subtask.
By adding these conditions, your program becomes more robust and can handle multiple subtasks automatically. Remember that in actual competitive programming contests, unless specified, you usually need to write a solution that passes all subtasks, but for testing or practice purposes, dividing the problem like this can be very helpful.