oj.uz

Submission #791878

# Submission time Handle Problem Language Result Execution time Memory
791878 2023-07-24T12:02:17 Z 12345678 Museum (CEOI17_museum) C++17
100 / 100
 643 ms 784784 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=1e4+5;
int n, k, x, dp[2][nx][nx], u, v, w, cnt[nx];
vector<vector<pair<int, int>>> d(nx);

void dfs(int u, int p)
{
    cnt[u]=1; dp[0][u][1]=dp[1][u][1]=0;
    for (auto [v, w]:d[u])
    {
        if (v==p) continue;
        dfs(v, u);
        for (int i=cnt[u]; i>=0; i--)
        {
            for (int j=cnt[v]; j>=1; j--)
            {
                dp[0][u][i+j]=min(dp[0][u][i+j], dp[0][u][i]+dp[0][v][j]+2*w);
                dp[1][u][i+j]=min(dp[1][u][i+j], dp[1][u][i]+dp[0][v][j]+2*w);
                dp[1][u][i+j]=min(dp[1][u][i+j], dp[0][u][i]+dp[1][v][j]+w);
            }
        }
        cnt[u]+=cnt[v];
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k>>x;
    for (int i=0; i<n-1; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w});
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) dp[0][i][j]=dp[1][i][j]=INT_MAX;
    dfs(x, x);
    cout<<dp[1][x][k];
}

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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 784304 KB Output is correct
2 Correct 454 ms 784208 KB Output is correct
3 Correct 494 ms 784668 KB Output is correct
4 Correct 454 ms 784468 KB Output is correct
5 Correct 453 ms 784224 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 784304 KB Output is correct
2 Correct 454 ms 784208 KB Output is correct
3 Correct 494 ms 784668 KB Output is correct
4 Correct 454 ms 784468 KB Output is correct
5 Correct 453 ms 784224 KB Output is correct
6 Correct 434 ms 784204 KB Output is correct
7 Correct 473 ms 784628 KB Output is correct
8 Correct 477 ms 784316 KB Output is correct
9 Correct 464 ms 784200 KB Output is correct
10 Correct 444 ms 784204 KB Output is correct

Subtask #4
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
6 Correct 643 ms 784304 KB Output is correct
7 Correct 454 ms 784208 KB Output is correct
8 Correct 494 ms 784668 KB Output is correct
9 Correct 454 ms 784468 KB Output is correct
10 Correct 453 ms 784224 KB Output is correct
11 Correct 434 ms 784204 KB Output is correct
12 Correct 473 ms 784628 KB Output is correct
13 Correct 477 ms 784316 KB Output is correct
14 Correct 464 ms 784200 KB Output is correct
15 Correct 444 ms 784204 KB Output is correct
16 Correct 442 ms 784316 KB Output is correct
17 Correct 461 ms 784204 KB Output is correct
18 Correct 472 ms 784488 KB Output is correct
19 Correct 476 ms 784272 KB Output is correct
20 Correct 481 ms 784332 KB Output is correct
21 Correct 462 ms 784564 KB Output is correct
22 Correct 452 ms 784220 KB Output is correct
23 Correct 481 ms 784320 KB Output is correct
24 Correct 445 ms 784312 KB Output is correct
25 Correct 501 ms 784784 KB Output is correct