Submission #1154891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154891		AndrijaM	Museum (CEOI17_museum)	C++20	100 / 100	485 ms	785920 KiB

museum

#include <bits/stdc++.h>

using namespace std;

///#define int long long

const int maxn=1e4+10;
int sz[maxn];
int dp[2][maxn][maxn];
vector<pair<int,int>>g[maxn];
int n,k,x,a,b,c;

void dfs(int node,int par)
{
    dp[1][node][1]=dp[0][node][1]=0;
    sz[node]=1;
    for(auto ax:g[node])
    {
        if(ax.first==par)continue;
        dfs(ax.first,node);
        for(int i=min(k,sz[node]+sz[ax.first]);i>=2;i--)
        {
            for(int j=min(i-1,sz[ax.first]);j>=max(1,i-sz[node]);j--)
            {
                dp[1][node][i]=min({dp[1][node][i],dp[0][node][i-j]+dp[1][ax.first][j]+ax.second,dp[1][node][i-j]+dp[0][ax.first][j]+2*ax.second});
                dp[0][node][i]=min(dp[0][node][i],dp[0][node][i-j]+dp[0][ax.first][j]+2*ax.second);
            }
        }
        sz[node]+=sz[ax.first];
    }
}

signed main()
{
    cin>>n>>k>>x;
    for(int i=0;i<n-1;i++)
    {
        cin>>a>>b>>c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    for(int i=0;i<maxn;i++)
    {
        for(int j=0;j<maxn;j++)
        {
            dp[0][i][j]=dp[1][i][j]=1e9;
        }
    }
    dfs(x,-1);
    cout<<dp[1][x][k]<<endl;
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20