oj.uz

Submission #780492

# Submission time Handle Problem Language Result Execution time Memory
780492 2023-07-12T09:29:24 Z quochuy147 Museum (CEOI17_museum) C++14
100 / 100
 289 ms 140420 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define file "name" 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}
 
const int mod = 1e9 + 7;
const int N = 1e4 + 2;
const int inf = 1e9;
 
int n, k, x;
int sz[N];
vector <int> f[N][2];
vector <pii> a[N];
 
void inp()
{
    cin >> n >> k >> x;
    for(int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        a[u].pb({v, w});
        a[v].pb({u, w});
    }
}
 
void size_subtree(int u, int pre) {
    sz[u] = 1;
    for(auto v : a[u]) {
        if(v.fi == pre) continue;
        size_subtree(v.fi, u);
        sz[u] += sz[v.fi];
    }
}
 
void dfs(int u, int pre) {
    f[u][0].resize(min(k, sz[u]) + 2, inf);
    f[u][1].resize(min(k, sz[u]) + 2, inf);
    f[u][0][0] = f[u][0][1] = f[u][1][0] = f[u][1][1] = 0;
    int tot = 1;
    for(auto e : a[u]) {
        int v = e.fi, w = e.se;
        if(v == pre) continue;
        dfs(v, u);
        tot += sz[v];
        for(int i = tot; i >= 2; --i) {
            if(i > k) continue;
            for(int j = max(0, i - tot + sz[v]); j <= min(i, sz[v]); ++j) {
                minimize(f[u][0][i], f[u][0][i - j] + f[v][1][j] + 2 * w);
                minimize(f[u][0][i], f[u][1][i - j] + f[v][0][j] + w);
                minimize(f[u][1][i], f[u][1][i - j] + f[v][1][j] + 2 * w);
            }
        }
    }
}
 
void solve()
{
    size_subtree(x, x);
    dfs(x, x);
    cout << f[x][0][k];
}
 
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    // freopen(file".inp" , "r" , stdin);
    // freopen(file".out" , "w" , stdout);
    inp();
    solve();
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2516 KB Output is correct
2 Correct 12 ms 2516 KB Output is correct
3 Correct 58 ms 5028 KB Output is correct
4 Correct 26 ms 3796 KB Output is correct
5 Correct 13 ms 3284 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2516 KB Output is correct
2 Correct 12 ms 2516 KB Output is correct
3 Correct 58 ms 5028 KB Output is correct
4 Correct 26 ms 3796 KB Output is correct
5 Correct 13 ms 3284 KB Output is correct
6 Correct 9 ms 2260 KB Output is correct
7 Correct 41 ms 4784 KB Output is correct
8 Correct 95 ms 2068 KB Output is correct
9 Correct 77 ms 2072 KB Output is correct
10 Correct 19 ms 2132 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 10 ms 2516 KB Output is correct
7 Correct 12 ms 2516 KB Output is correct
8 Correct 58 ms 5028 KB Output is correct
9 Correct 26 ms 3796 KB Output is correct
10 Correct 13 ms 3284 KB Output is correct
11 Correct 9 ms 2260 KB Output is correct
12 Correct 41 ms 4784 KB Output is correct
13 Correct 95 ms 2068 KB Output is correct
14 Correct 77 ms 2072 KB Output is correct
15 Correct 19 ms 2132 KB Output is correct
16 Correct 29 ms 2984 KB Output is correct
17 Correct 75 ms 3416 KB Output is correct
18 Correct 66 ms 16260 KB Output is correct
19 Correct 118 ms 1984 KB Output is correct
20 Correct 27 ms 2444 KB Output is correct
21 Correct 186 ms 77384 KB Output is correct
22 Correct 94 ms 3808 KB Output is correct
23 Correct 289 ms 2248 KB Output is correct
24 Correct 102 ms 2892 KB Output is correct
25 Correct 258 ms 140420 KB Output is correct