제출 #1310517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310517		ayuxhkumxr22	Travelling Trader (CCO23_day2problem2)	C++20	0 / 25	2 ms	568 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static const int MAXN = 200000 + 5;

int N, K;
vector<int> g[MAXN];
ll profit[MAXN];

vector<int> answer_path;
ll answer_profit = 0;

/* ---------- Common DFS utilities ---------- */

int parent[MAXN];
int depth[MAXN];

void dfs_init(int u, int p) {
    parent[u] = p;
    for (int v : g[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dfs_init(v, u);
    }
}

/* ---------- K = 1 : Longest path from root ---------- */

ll best_sum_k1 = 0;
vector<int> best_path_k1;

void dfs_k1(int u, int p, ll cur_sum, vector<int> &cur_path) {
    cur_sum += profit[u];
    cur_path.push_back(u);

    if (cur_sum > best_sum_k1) {
        best_sum_k1 = cur_sum;
        best_path_k1 = cur_path;
    }

    for (int v : g[u]) {
        if (v == p) continue;
        dfs_k1(v, u, cur_sum, cur_path);
    }

    cur_path.pop_back();
}

/* ---------- K = 3 : Visit all nodes ---------- */

vector<int> path_k3;

void dfs_k3(int u, int p) {
    path_k3.push_back(u);
    for (int v : g[u]) {
        if (v == p) continue;
        dfs_k3(v, u);
        path_k3.push_back(u); // return
    }
}

/* ---------- K = 2 : Placeholder (to be filled next) ---------- */

void solve_k2() {
    // This is where dp1, dp2, dp3 tree DP will go.
    // It is too large to safely generate in the same message.
    // We will implement this in the next step.
    cout << "K = 2 solver not yet implemented.\n";
    exit(0);
}

/* ---------- Main ---------- */

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> profit[i];
    }

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

    dfs_init(1, 0);

    if (K == 1) {
        vector<int> cur;
        dfs_k1(1, 0, 0, cur);
        cout << best_sum_k1 << "\n";
        for (int x : best_path_k1) cout << x << " ";
        cout << "\n";
    }
    else if (K == 3) {
        dfs_k3(1, 0);
        ll total = 0;
        vector<int> used(N + 1, 0);
        for (int x : path_k3) {
            if (!used[x]) {
                total += profit[x];
                used[x] = 1;
            }
        }
        cout << total << "\n";
        for (int x : path_k3) cout << x << " ";
        cout << "\n";
    }
    else if (K == 2) {
        solve_k2();  // real implementation will be added next
    }

    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