Submission #1133900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133900		CDuong	Travelling Trader (CCO23_day2problem2)	C++20	2 / 25	92 ms	31416 KiB

Main

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define int long long
#define isz(x) (int)x.size()
using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;

    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    if (k == 1) {
        vector<int> dp(n), par(n);
        pair<int, int> res = {0, -1};
        auto dfs = [&](auto self, int u, int p) -> void {
            par[u] = p;
            dp[u] += a[u];
            res = max(res, {dp[u], u});
            for (auto v : g[u]) if (v != p) {
                dp[v] = dp[u];
                self(self, v, u);
            }
        };
        dfs(dfs, 0, -1);
        vector<int> trace;
        int u = res.second;
        cout << res.first << endl;
        while (u != -1) {
            trace.emplace_back(u);
            u = par[u];
        }
        reverse(all(trace));
        cout << isz(trace) << endl;
        for (auto u : trace) cout << u + 1 << " \n"[u == trace.back()];
        return;
    }
    if (k == 2) {
        vector<int> dp(n), par(n);
        pair<int, int> res = {0, -1};
        auto dfs = [&](auto self, int u, int p) -> void {
            par[u] = p;
            dp[u] += a[u];
            res = max(res, {dp[u], u});
            int tot = 0;
            for (auto v : g[u]) if (v != p) {
                tot += a[v];
            }
            for (auto v : g[u]) if (v != p) {
                dp[v] = dp[u] + tot - a[v];
                self(self, v, u);
            }
        };
        dfs(dfs, 0, -1);
        vector<int> trace;
        int u = res.second;
        while (u != -1) {
            trace.emplace_back(u);
            u = par[u];
        }
        reverse(all(trace));
        vector<int> rtrace = {0};
        for (int i = 0; i + 1 < isz(trace); ++i) {
            int pu = trace[i], nu = trace[i + 1];
            for (auto v : g[pu]) if (v != nu and v != par[pu]) {
                rtrace.emplace_back(v);
            }
            rtrace.emplace_back(nu);
        }
        cout << res.first << endl << isz(rtrace) << endl;
        for (int i = 0; i < isz(rtrace); ++i) {
            cout << rtrace[i] + 1 << " \n"[i + 1 == isz(rtrace)];
        }
    }
}

signed main() {

#ifndef CDuongg
    if (fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

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