Submission #952141

#	Time	Username	Problem	Language	Result	Execution time	Memory
952141		vjudge1	Museum (CEOI17_museum)	C++17	100 / 100	463 ms	784916 KiB

museum

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
const int maxv = 1e4 + 5;
using ll = long long;
int dp[maxn][maxv][2];
int n, k;
vector<pair<int, int>> G[maxn];
int st;
int siz[maxn];
void dfs(int x, int fa)
{
	siz[x] = 1;
    for (auto p : G[x])
    {
        int y = p.first;
        int w = p.second;
        if (y == fa)
            continue;
        dfs(y, x);
        for (int i = min(k, siz[x]); i >= 0; i--)
        {
            for (int j = 0; j <= min(k - i, siz[y]); j++)
            {
                dp[x][i + j][0] = min(dp[x][i + j][0], dp[x][i][0] + dp[y][j][0] + w * 2);
                dp[x][i + j][1] = min(dp[x][i + j][1], dp[x][i][1] + dp[y][j][0] + w * 2);
                dp[x][i + j][1] = min(dp[x][i + j][1], dp[x][i][0] + dp[y][j][1] + w);
            }
        }
        siz[x] += siz[y]; 
    }
}
int main()
{
//    freopen("museum.in", "r", stdin);
//    freopen("museum.out", "w", stdout);
    scanf("%d%d%d", &n, &k, &st);
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        int x;
        scanf("%d%d%d", &u, &v, &x);
        G[u].push_back(make_pair(v, x));
        G[v].push_back(make_pair(u, x));
    }
    if(k == 1){
    	printf("0\n");
    	return 0;
	}
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= n; i++)
    {
        dp[i][1][0] = dp[i][1][1] = 0;
    }
    dfs(st, 0);
    printf("%d\n", min(dp[st][k][1], dp[st][k][0]));
    return 0;
}

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d%d%d", &n, &k, &st);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%d%d%d", &u, &v, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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