oj.uz

Submission #778835

# Submission time Handle Problem Language Result Execution time Memory
778835 2023-07-10T19:50:19 Z borisAngelov Museum (CEOI17_museum) C++17
0 / 100
 1018 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 10005;
const int inf = 1000000000;

int n, k, start;

vector<pair<int, int>> g[maxn];

int dp1[maxn][maxn];
int dp2[maxn][maxn];

int subtree_size[maxn];

void dfs(int node, int par)
{
    subtree_size[node] = 1;

    for (auto [next_node, w] : g[node])
    {
        if (next_node != node)
        {
            dfs(next_node, node);
        }
    }

    dp1[node][1] = 0;
    dp2[node][1] = 0;

    for (auto [next_node, w] : g[node])
    {
        if (next_node != node)
        {
            for (int i = subtree_size[node]; i >= 0; --i)
            {
                for (int j = subtree_size[next_node]; j >= 0; --j)
                {
                    dp1[node][i + j] = min(dp1[node][i + j], dp1[node][i] + dp2[next_node][j] + 2 * w);
                    dp2[node][i + j] = min(dp2[node][i + j], dp2[node][i] + dp1[next_node][j] + 2 * w);
                    dp2[node][i + j] = min(dp2[node][i + j], dp1[node][i] + dp2[next_node][j] + 1 * w);
                    dp2[node][i + j] = min(dp2[node][i + j], dp1[node][i] + dp1[next_node][j] + 1 * w);
                }
            }
        }
    }
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> k >> start;

    for (int i = 1; i <= n - 1; ++i)
    {
        int x, y, w;
        cin >> x >> y >> w;

        g[x].push_back(make_pair(y, w));
        g[y].push_back(make_pair(x, w));
    }

    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j <= n; ++j)
        {
            dp1[i][j] = 0;
            dp2[i][j] = 0;
        }
    }

    dfs(start, -1);

    cout << dp2[start][k] << endl;

    return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 35.0

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

Subtask #4
0 / 20.0

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