oj.uz

Submission #952141

# Submission time Handle Problem Language Result Execution time Memory
952141 2024-03-23T06:38:36 Z vjudge1 Museum (CEOI17_museum) C++17
100 / 100
 463 ms 784916 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 784208 KB Output is correct
2 Correct 215 ms 784208 KB Output is correct
3 Correct 218 ms 784208 KB Output is correct
4 Correct 217 ms 784236 KB Output is correct
5 Correct 218 ms 784212 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 784508 KB Output is correct
2 Correct 237 ms 784552 KB Output is correct
3 Correct 237 ms 784836 KB Output is correct
4 Correct 226 ms 784724 KB Output is correct
5 Correct 227 ms 784688 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 784508 KB Output is correct
2 Correct 237 ms 784552 KB Output is correct
3 Correct 237 ms 784836 KB Output is correct
4 Correct 226 ms 784724 KB Output is correct
5 Correct 227 ms 784688 KB Output is correct
6 Correct 225 ms 784408 KB Output is correct
7 Correct 227 ms 784824 KB Output is correct
8 Correct 226 ms 784464 KB Output is correct
9 Correct 228 ms 784572 KB Output is correct
10 Correct 224 ms 784468 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 784208 KB Output is correct
2 Correct 215 ms 784208 KB Output is correct
3 Correct 218 ms 784208 KB Output is correct
4 Correct 217 ms 784236 KB Output is correct
5 Correct 218 ms 784212 KB Output is correct
6 Correct 225 ms 784508 KB Output is correct
7 Correct 237 ms 784552 KB Output is correct
8 Correct 237 ms 784836 KB Output is correct
9 Correct 226 ms 784724 KB Output is correct
10 Correct 227 ms 784688 KB Output is correct
11 Correct 225 ms 784408 KB Output is correct
12 Correct 227 ms 784824 KB Output is correct
13 Correct 226 ms 784464 KB Output is correct
14 Correct 228 ms 784572 KB Output is correct
15 Correct 224 ms 784468 KB Output is correct
16 Correct 249 ms 784516 KB Output is correct
17 Correct 301 ms 784644 KB Output is correct
18 Correct 251 ms 784916 KB Output is correct
19 Correct 279 ms 784468 KB Output is correct
20 Correct 245 ms 784648 KB Output is correct
21 Correct 354 ms 784824 KB Output is correct
22 Correct 318 ms 784464 KB Output is correct
23 Correct 463 ms 784616 KB Output is correct
24 Correct 325 ms 784468 KB Output is correct
25 Correct 383 ms 784844 KB Output is correct