oj.uz

Submission #793905

# Submission time Handle Problem Language Result Execution time Memory
793905 2023-07-26T07:56:54 Z 이성호(#10059) Travelling Trader (CCO23_day2problem2) C++17
2 / 25
 253 ms 28292 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
const int inf = 1e18;
int N, K, a[200005];
vector<int> adj[200005];

namespace one
{
    int tot[200005], par[200005], val[200005];
    void dfs(int v, int p)
    {
        par[v] = p;
        val[v] = val[p] + a[v];
        for (int i:adj[v]) {
            if (i != p) {
                dfs(i, v);
            }
        }
    }
}

namespace two
{
    pair<int, int> dp[200005][2];
    vector<int> tour;
    void dfs(int v, int p)
    {
        for (int i:adj[v]) {
            if (i != p) {
                dfs(i, v);
            }
        }
        dp[v][0].first += a[v];
        int mx = -inf, id = -1;
        for (int i:adj[v]) {
            if (i != p) {
                dp[v][0].first += a[i];
                if (mx < dp[i][1].first - a[i]) {
                    mx = dp[i][1].first - a[i];
                    id = i;
                }
            }
        }
        dp[v][0] = make_pair(dp[v][0].first + mx, id);
        for (int i:adj[v]) {
            if (i != p) {
                dp[v][1].first += a[i];
            }
        }
        for (int i:adj[v]) {
            if (i != p) {
                if (dp[v][1].first < dp[i][0].first) {
                    dp[v][1].first = dp[i][0].first;
                    dp[v][1].second = i;
                }
            }
        }
        dp[v][1].first += a[v];
    }
    void track(int v, int p, bool k)
    {
        if (!k) {
            tour.push_back(v);
            int nxt = dp[v][0].second;
            track(nxt, v, true);
            for (int i:adj[v]) {
                if (i != p && i != nxt) tour.push_back(i);
            }
        }
        else {
            if (!dp[v][1].second) {
                for (int i:adj[v]) {
                    if (i != p) tour.push_back(i);
                }
            }
            else {
                int nxt = dp[v][1].second;
                track(nxt, v, false);
            }
            tour.push_back(v);
        }
    }
}

signed main()
{
    cin >> N >> K;
    for (int i = 1; i < N; 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 >> a[i];
    if (K == 1) {
        one::dfs(1, 0);
        int v = max_element(one::val + 1, one::val + N + 1) - one::val;
        vector<int> vc(1, v);
        while (vc.back() != 1) vc.push_back(one::par[vc.back()]);
        reverse(vc.begin(), vc.end());
        cout << one::val[v] << '\n';
        cout << vc.size() << '\n';
        for (int i:vc) cout << i << ' ';
        cout << '\n';
    }
    else if (K == 2) {
        two::dfs(1, 0);
        two::track(1, 0, 0);
        cout << two::dp[1][0].first << '\n';
        cout << two::tour.size() << '\n';
        for (int i:two::tour) cout << i << ' ';
        cout << '\n';
    }
    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 5096 KB Output is correct
3 Correct 165 ms 17096 KB Output is correct
4 Correct 203 ms 17168 KB Output is correct
5 Correct 203 ms 17020 KB Output is correct
6 Correct 183 ms 17836 KB Output is correct
7 Correct 148 ms 17464 KB Output is correct
8 Correct 201 ms 16708 KB Output is correct
9 Correct 253 ms 28292 KB Output is correct
10 Correct 234 ms 24576 KB Output is correct
11 Correct 160 ms 17460 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 2 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 2 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 2 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5076 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5076 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -