oj.uz

Submission #778837

# Submission time Handle Problem Language Result Execution time Memory
778837 2023-07-10T19:53:41 Z borisAngelov Museum (CEOI17_museum) C++17
20 / 100
 1034 ms 784684 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 10005;
const int inf = 2000000000;

int n, k, start;

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

unsigned int dp1[maxn][maxn];
unsigned 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 != par)
        {
            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] + dp1[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);
                }
            }

            subtree_size[node] += subtree_size[next_node];
        }
    }
}

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] = inf;
            dp2[i][j] = inf;
        }
    }

    dfs(start, -1);

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

    return 0;
}

/*
11 8 3
1 3 3
3 2 5
6 4 5
1 11 3
9 1 2
9 10 2
3 7 10
6 7 1
7 8 1
7 5 1
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 784224 KB Output is correct
2 Correct 803 ms 784224 KB Output is correct
3 Incorrect 1034 ms 784684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 784224 KB Output is correct
2 Correct 803 ms 784224 KB Output is correct
3 Incorrect 1034 ms 784684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 803 ms 784224 KB Output is correct
7 Correct 803 ms 784224 KB Output is correct
8 Incorrect 1034 ms 784684 KB Output isn't correct
9 Halted 0 ms 0 KB -