oj.uz

Submission #952000

# Submission time Handle Problem Language Result Execution time Memory
952000 2024-03-23T03:35:19 Z vjudge1 Museum (CEOI17_museum) C++17
80 / 100
 3000 ms 784984 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);
        siz[x] += siz[y]; 
        for (int i = min(k, siz[x]); i >= 0; i--)
        {
            for (int j = 0; j <= min(i - 1, siz[y]); j++)
            {
                dp[x][i][0] = min(dp[x][i][0], dp[x][i - j - 1][0] + dp[y][j][0] + w * 2);
                dp[x][i][1] = min(dp[x][i][1], dp[x][i - j - 1][1] + dp[y][j][0] + w * 2);
                dp[x][i][1] = min(dp[x][i][1], dp[x][i - j - 1][0] + dp[y][j][1] + w);
            }
            dp[x][i][1] = min(dp[x][i][1], dp[x][0][0] + dp[y][i][1] + w);
        }
    }
}
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][0][0] = dp[i][0][1] = 0;
    }
    dfs(st, 0);
    printf("%d\n", dp[st][k - 1][1]);
    return 0;
}

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 784208 KB Output is correct
2 Correct 208 ms 784012 KB Output is correct
3 Correct 336 ms 784324 KB Output is correct
4 Correct 207 ms 784208 KB Output is correct
5 Correct 207 ms 784208 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 784708 KB Output is correct
2 Correct 219 ms 784464 KB Output is correct
3 Correct 253 ms 784984 KB Output is correct
4 Correct 244 ms 784976 KB Output is correct
5 Correct 240 ms 784576 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 784708 KB Output is correct
2 Correct 219 ms 784464 KB Output is correct
3 Correct 253 ms 784984 KB Output is correct
4 Correct 244 ms 784976 KB Output is correct
5 Correct 240 ms 784576 KB Output is correct
6 Correct 217 ms 784464 KB Output is correct
7 Correct 249 ms 784816 KB Output is correct
8 Correct 220 ms 784464 KB Output is correct
9 Correct 234 ms 784656 KB Output is correct
10 Correct 216 ms 784664 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 784208 KB Output is correct
2 Correct 208 ms 784012 KB Output is correct
3 Correct 336 ms 784324 KB Output is correct
4 Correct 207 ms 784208 KB Output is correct
5 Correct 207 ms 784208 KB Output is correct
6 Correct 222 ms 784708 KB Output is correct
7 Correct 219 ms 784464 KB Output is correct
8 Correct 253 ms 784984 KB Output is correct
9 Correct 244 ms 784976 KB Output is correct
10 Correct 240 ms 784576 KB Output is correct
11 Correct 217 ms 784464 KB Output is correct
12 Correct 249 ms 784816 KB Output is correct
13 Correct 220 ms 784464 KB Output is correct
14 Correct 234 ms 784656 KB Output is correct
15 Correct 216 ms 784664 KB Output is correct
16 Correct 276 ms 784648 KB Output is correct
17 Correct 753 ms 784532 KB Output is correct
18 Correct 1997 ms 784812 KB Output is correct
19 Correct 268 ms 784468 KB Output is correct
20 Correct 250 ms 784468 KB Output is correct
21 Execution timed out 3096 ms 784724 KB Time limit exceeded
22 Halted 0 ms 0 KB -