oj.uz

Submission #860147

# Submission time Handle Problem Language Result Execution time Memory
860147 2023-10-11T19:33:13 Z ThegeekKnight16 Chase (CEOI17_chase) C++17
0 / 100
 306 ms 524288 KB 
#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)
{
    for (int k = 1; k <= V; k++) resp = max(resp, dp[v][k].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.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 306 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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