oj.uz

Submission #1119162

# Submission time Handle Problem Language Result Execution time Memory
1119162 2024-11-26T16:48:09 Z LonlyR Museum (CEOI17_museum) C++17
100 / 100
 409 ms 784972 KB 
#include<bits/stdc++.h>

using namespace std;
const int maxn = 10004;
int n, k, x;
int f[maxn][maxn], g[maxn][maxn], sub[maxn];
vector<pair<int,int>> adj[maxn];

inline void MIN(int &x, int y)
{
    x = min(x, y);
}

void merge(int x, int y, int w)
{
    for (int i = sub[x]; i >= 0; i--)
        for (int j = sub[y]; j >= 0; j--)
        {
            MIN(f[x][i + j], min(f[x][i] + g[y][j] + w * 2, g[x][i] + f[y][j] + w));
            MIN(g[x][i + j], g[x][i] + g[y][j] + w * 2);
        }
    sub[x] += sub[y];
}

void dfs(int x, int p = 0)
{
    f[x][1] = g[x][1] = 0;
    sub[x] = 1;
    for (auto [i, j] : adj[x]) if (i != p)
    {
        dfs(i, x);
        merge(x, i, j);
    }
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> k >> x;
    for (int i = 1, u, v, w; i < n; i++)
        cin >> u >> v >> w,
        adj[u].emplace_back(v, w),
        adj[v].emplace_back(u, w);
    memset(f, 0x3f, sizeof f);
    memset(g, 0x3f, sizeof g);
    dfs(x);
    cout << min(f[x][k], g[x][k]);
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 783948 KB Output is correct
2 Correct 102 ms 783904 KB Output is correct
3 Correct 106 ms 783920 KB Output is correct
4 Correct 104 ms 783948 KB Output is correct
5 Correct 110 ms 783972 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 784716 KB Output is correct
2 Correct 222 ms 784676 KB Output is correct
3 Correct 286 ms 784872 KB Output is correct
4 Correct 238 ms 784728 KB Output is correct
5 Correct 214 ms 784428 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 784716 KB Output is correct
2 Correct 222 ms 784676 KB Output is correct
3 Correct 286 ms 784872 KB Output is correct
4 Correct 238 ms 784728 KB Output is correct
5 Correct 214 ms 784428 KB Output is correct
6 Correct 222 ms 784460 KB Output is correct
7 Correct 261 ms 784972 KB Output is correct
8 Correct 394 ms 784604 KB Output is correct
9 Correct 315 ms 784460 KB Output is correct
10 Correct 217 ms 784588 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 783948 KB Output is correct
2 Correct 102 ms 783904 KB Output is correct
3 Correct 106 ms 783920 KB Output is correct
4 Correct 104 ms 783948 KB Output is correct
5 Correct 110 ms 783972 KB Output is correct
6 Correct 210 ms 784716 KB Output is correct
7 Correct 222 ms 784676 KB Output is correct
8 Correct 286 ms 784872 KB Output is correct
9 Correct 238 ms 784728 KB Output is correct
10 Correct 214 ms 784428 KB Output is correct
11 Correct 222 ms 784460 KB Output is correct
12 Correct 261 ms 784972 KB Output is correct
13 Correct 394 ms 784604 KB Output is correct
14 Correct 315 ms 784460 KB Output is correct
15 Correct 217 ms 784588 KB Output is correct
16 Correct 250 ms 784460 KB Output is correct
17 Correct 213 ms 784536 KB Output is correct
18 Correct 231 ms 784716 KB Output is correct
19 Correct 342 ms 784460 KB Output is correct
20 Correct 267 ms 784540 KB Output is correct
21 Correct 250 ms 784716 KB Output is correct
22 Correct 280 ms 784676 KB Output is correct
23 Correct 409 ms 784680 KB Output is correct
24 Correct 250 ms 784660 KB Output is correct
25 Correct 368 ms 784900 KB Output is correct