Submission #1309571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309571		ayuxhkumxr22	Travelling Trader (CCO23_day2problem2)	C++20	0 / 25	8 ms	1088 KiB

Main

/**
 * Solution for CCO 2023 Day 2 Problem 2: Travelling Trader
 * * Logic:
 * This is a Tree DP problem where we must select a subset of nodes and a traversal order.
 * Constraint: Distance between consecutive profit-takes <= K.
 * * DP State: dp[u][d_in]
 * d_in: The distance from the last selected ancestor.
 * Returns: A list of Pareto-optimal results {profit, d_out}.
 * d_out: The distance from the last selected node in this subtree to u's parent.
 * * Strategies at node u:
 * 1. Pick u FIRST: Reset gap to 0 immediately. Then visit children. 
 * - Good for: Maximizing profit within the subtree (provides gap 1 to children).
 * 2. Pick u LAST: Visit children first (passing d_in), then pick u.
 * - Good for: Returning a small gap (1) to the parent.
 * 3. SKIP u: Visit children passing d_in.
 * - Good for: When picking u is impossible or suboptimal (rare).
 * * Greedy Chain Logic:
 * To merge children results, we use a greedy strategy:
 * Always visit the child that allows continuation (valid input gap) and returns the 
 * SMALLEST output gap. This keeps the "gap budget" loose for subsequent children.
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// --- Constants & Globals ---
const int MAXN = 200005;

struct State {
    int d_out;
    long long profit;
};

// Result for a child's greedy consideration
struct ChildMove {
    int next_req_in; // The input gap this child needs
    int ret_out;     // The output gap this child returns
    long long profit;
    int child_idx;   // Original index
};

int N, K;
vector<int> adj[MAXN];
vector<int> tree[MAXN];
long long P[MAXN];

// dp[u][d_in] -> List of {d_out, profit}
// d_in ranges 1..K (since d_in=0 is impossible for a child, parent dist >= 1)
// We map 0-based index to 1..K
vector<State> dp[MAXN][4]; 

// --- Helper Functions ---

void build_tree(int u, int p) {
    for (int v : adj[u]) {
        if (v != p) {
            tree[u].push_back(v);
            build_tree(v, u);
        }
    }
}

// Keep only pareto optimal states: Max profit for each d_out
void optimize_states(vector<State>& states) {
    if (states.empty()) return;
    
    // We want to map each d_out (1..K) to max profit.
    // Since K is small, just use a fixed array.
    long long best_p[5];
    fill(best_p, best_p + 5, -1);
    
    for (auto& s : states) {
        if (s.d_out <= K+1) { // d_out can be K+1 (invalid/end), but we filter later
             // For strict pareto: if we have d_out=1, profit=10, 
             // and d_out=2, profit=10, the d_out=2 is useless.
             // But simpler: just map best profit per d_out.
             if (s.profit > best_p[s.d_out]) best_p[s.d_out] = s.profit;
        }
    }
    
    states.clear();
    // Reconstruct pareto frontier
    long long max_so_far = -1;
    // Iterate from largest gap to smallest. 
    // If smaller gap doesn't have more profit, it's useless? 
    // No, smaller gap is structurally better.
    // If larger gap has MORE profit, we keep it.
    // If smaller gap has LESS profit, we keep it (structural advantage).
    
    for (int d = 1; d <= K + 1; d++) {
        if (best_p[d] != -1) {
             states.push_back({d, best_p[d]});
        }
    }
}

// Execute Greedy Chain Strategy
// start_gap: Gap before visiting first child
// force_u_last: If true, we append u at the end
// u_picked_first: If true, we already took profit P[u], start_gap should be 0.
State solve_chain(int u, int start_gap, bool force_u_last, bool u_picked_first) {
    long long current_profit = (u_picked_first ? P[u] : 0);
    int current_gap = start_gap;
    
    // If we skip u and start_gap >= K, we can't do anything (input to child must be <= K)
    // Child input = current_gap + 1. So we need current_gap < K.
    if (!u_picked_first && !force_u_last && start_gap >= K) return {start_gap + 1, -1}; // Invalid

    // Collect best moves from all children
    // Since greedy selection depends on current_gap, and current_gap changes,
    // we normally re-evaluate. BUT K is small.
    // We can pre-calculate the best move each child offers for input 1, 2, 3...
    // Then dynamically pick.
    
    // Store child options: options[v][input_gap] = {ret_gap, profit}
    // Optimization: Since we simply want "Smallest Return Gap", we can sort children.
    // However, a child might accept input 1 but not 2.
    // Let's use a "used" mask.
    
    vector<bool> used(tree[u].size(), false);
    
    while (true) {
        int req_in = current_gap + 1;
        if (req_in > K) break; // Cannot enter any child
        
        int best_child = -1;
        int best_ret = 100;
        long long best_gain = -1;
        
        // Scan children
        for (int i = 0; i < tree[u].size(); i++) {
            if (used[i]) continue;
            int v = tree[u][i];
            
            // Look up dp[v][req_in]
            // We want the option with Min d_out, then Max profit
            for (auto& s : dp[v][req_in]) {
                // Return from child is s.d_out.
                // New gap at u will be s.d_out + 1.
                // We want s.d_out to be small.
                if (s.d_out < best_ret) {
                    best_ret = s.d_out;
                    best_gain = s.profit;
                    best_child = i;
                } else if (s.d_out == best_ret) {
                    if (s.profit > best_gain) {
                        best_gain = s.profit;
                        best_child = i;
                    }
                }
            }
        }
        
        if (best_child != -1) {
            used[best_child] = true;
            current_profit += best_gain;
            current_gap = best_ret; // gap at u becomes child's return
            // Wait, gap at u becomes child_out + 1?
            // DP state stores d_out relative to PARENT.
            // s.d_out is distance from Child's profit to Child's Parent (u).
            // So s.d_out is exactly the gap at u upon return.
            // Correct.
        } else {
            break;
        }
    }
    
    if (force_u_last) {
        // We try to append u
        // Valid if current_gap + 1 <= K?
        // No, "gap" is distance from last profit.
        // We are at u. Distance is current_gap.
        // If we pick u, distance becomes 0.
        // Condition: current_gap <= K. (Actually distance from last profit).
        // Since we enforced req_in <= K for children steps, current_gap is always valid dist?
        // Yes, current_gap is exactly dist to last profit.
        if (current_gap <= K) {
            current_profit += P[u];
            current_gap = 0;
        } else {
            return {100, -1}; // Fail
        }
    }
    
    // Final d_out relative to u's parent is current_gap + 1
    return {current_gap + 1, current_profit};
}

void solve(int u) {
    // Post-order DFS
    for (int v : tree[u]) solve(v);
    
    // Calculate for all incoming gaps
    for (int d_in = 1; d_in <= K; d_in++) {
        // Strategy 1: Pick First
        // Start gap 0.
        State s1 = solve_chain(u, 0, false, true);
        if (s1.profit != -1) dp[u][d_in].push_back(s1);
        
        // Strategy 2: Pick Last
        // Start gap d_in.
        State s2 = solve_chain(u, d_in, true, false);
        if (s2.profit != -1) dp[u][d_in].push_back(s2);
        
        // Strategy 3: Skip
        // Start gap d_in.
        State s3 = solve_chain(u, d_in, false, false);
        if (s3.profit != -1) dp[u][d_in].push_back(s3);
        
        optimize_states(dp[u][d_in]);
    }
}

// Global Path Reconstruction
vector<int> final_path;

void reconstruct(int u, int start_gap, int strategy) {
    // 1: Pick First, 2: Pick Last, 3: Skip
    
    bool u_picked_first = (strategy == 1);
    bool force_u_last = (strategy == 2);
    
    if (u_picked_first) final_path.push_back(u);
    
    int current_gap = (u_picked_first ? 0 : start_gap);
    vector<bool> used(tree[u].size(), false);
    
    // Re-run greedy loop to find child order
    while (true) {
        int req_in = current_gap + 1;
        if (req_in > K) break;
        
        int best_child = -1;
        int best_ret = 100;
        long long best_gain = -1;
        // Need to identify WHICH state of child was used?
        // We assumed we picked the optimal one. 
        // We need to match the specific outcome.
        
        // To simplify: Just look for the move that is "optimal" locally.
        // This works because the DP value was built using this exact greedy logic.
        
        for (int i = 0; i < tree[u].size(); i++) {
            if (used[i]) continue;
            int v = tree[u][i];
            for (auto& s : dp[v][req_in]) {
                if (s.d_out < best_ret) {
                    best_ret = s.d_out;
                    best_gain = s.profit;
                    best_child = i;
                } else if (s.d_out == best_ret) {
                    if (s.profit > best_gain) {
                        best_gain = s.profit;
                        best_child = i;
                    }
                }
            }
        }
        
        if (best_child != -1) {
            used[best_child] = true;
            // Recurse into child
            int v = tree[u][best_child];
            
            // Determine Child Strategy
            // We know child received req_in and produced best_gain/best_ret.
            // We check which strategy at child yields this.
            // Order preference: Pick First, Pick Last, Skip.
            // (Must match DP build order or logic).
            
            int child_strat = 0;
            // Check Strat 1
            bool found = false;
            // We need to re-call solve_chain or just peek DP?
            // DP stores merged results. We need to check hypothetical.
            // Since we don't store strategy source in DP, we check by re-solving.
            
            // Check Pick First (1)
            State c1 = solve_chain(v, 0, false, true);
            if (c1.d_out == best_ret + 1 && c1.profit == best_gain) child_strat = 1;
            else {
                // Check Pick Last (2)
                State c2 = solve_chain(v, req_in, true, false);
                if (c2.d_out == best_ret + 1 && c2.profit == best_gain) child_strat = 2;
                else child_strat = 3; // Skip
            }
            
            reconstruct(v, req_in, child_strat);
            
            current_gap = best_ret;
        } else {
            break;
        }
    }
    
    if (force_u_last) final_path.push_back(u);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> N >> K)) return 0;

    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= N; i++) cin >> P[i];

    build_tree(1, 0);
    solve(1);

    // Root (1) must be picked. 
    // It is equivalent to "Pick First" with dummy input.
    // Or just check which strategy at root yields max profit.
    // Since root is picked, only Strat 1 or 2 possible.
    
    long long ans = -1;
    int best_strat = 1;
    
    // Check Strat 1 (Pick First)
    State s1 = solve_chain(1, 0, false, true);
    if (s1.profit > ans) { ans = s1.profit; best_strat = 1; }
    
    // Check Strat 2 (Pick Last) -- Only valid if input valid? 
    // Root input is conceptually 0? No, root has no parent.
    // But "Pick Last" implies we traverse children BEFORE root.
    // Children would need input gap.
    // If we assume trader starts at 1, he is AT 1.
    // He can take profit immediately (Pick First).
    // Can he delay 1? "Trader starts by doing business in city 1".
    // Problem says: "starts by doing business in city 1".
    // So Strategy 1 (Pick First) is MANDATORY for root.
    
    ans = s1.profit;
    best_strat = 1;

    cout << ans << endl;
    
    reconstruct(1, 0, best_strat);
    
    cout << final_path.size() << endl;
    for (int i = 0; i < final_path.size(); i++) {
        cout << final_path[i] << (i == final_path.size() - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 7
• Subtask 3: 0 / 3
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5