Submission #860146

#	Time	Username	Problem	Language	Result	Execution time	Memory
860146		ThegeekKnight16	Chase (CEOI17_chase)	C++17	0 / 100	331 ms	524288 KiB

chase

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 10;
const int MAXV = 110;
array<vector<set<pair<int, int>>>, MAXN> dp;
array<vector<int>, MAXN> grafo;
array<int, MAXN> pom, pomviz;
int N, V;
int resp = 0;

void dfs(int v, int p)
{
    dp[v].resize(V+1, {make_pair(0, v)});
    // for (int i = 0; i <= V; i++) dp[v][i].emplace(0, v);
    pomviz[v] = 0;
    for (auto viz : grafo[v])
    {
        if (viz == p) continue;
        pomviz[v] += pom[viz];
    }

    for (auto viz : grafo[v])
    {
        if (viz == p) continue;
        dfs(viz, v);
        for (int k = 1; k <= V; k++)
        {
            dp[v][k].emplace(max(dp[viz][k].rbegin()->first, dp[viz][k-1].rbegin()->first + pomviz[v]), viz);
            while (dp[v][k].size() >= 4) dp[v][k].erase(dp[v][k].begin());
        }
    }
}

void girarArvore(int v, int p)
{
    resp = max(resp, dp[v][V].rbegin()->first);

    for (auto viz : grafo[v])
    {
        if (viz == p) continue;

        //Salva
        auto antv = dp[v]; int antpom = pomviz[v];
        auto antviz = dp[viz]; int antpomviz = pomviz[viz];

        //Gira
        for (int k = 1; k <= V; k++) dp[v][k].erase(make_pair(max(dp[viz][k].rbegin()->first, dp[viz][k-1].rbegin()->first + pomviz[v]), viz));
        pomviz[v] -= pom[viz]; pomviz[viz] += pom[v];
        for (int k = 1; k <= V; k++) dp[viz][k].emplace(max(dp[v][k].rbegin()->first, dp[v][k-1].rbegin()->first + pomviz[viz]), v);

        girarArvore(viz, v);

        //Volta
        dp[v] = antv; dp[viz] = antviz;
        pomviz[v] = antpom; pomviz[viz] = antpomviz;
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> V;
    for (int i = 1; i <= N; i++) cin >> pom[i];
    for (int i = 1; i < N; i++)
    {
        int X, Y;
        cin >> X >> Y;
        grafo[X].push_back(Y);
        grafo[Y].push_back(X);
    }
    dfs(1, 1);
    girarArvore(1, 1);
    cout << resp << '\n';
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30