oj.uz

Submission #780484

# Submission time Handle Problem Language Result Execution time Memory
780484 2023-07-12T09:24:22 Z quochuy147 Museum (CEOI17_museum) C++14
100 / 100
 260 ms 140424 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].assign(min(k, sz[u]) + 2, inf);
    f[u][1].assign(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 12 ms 2532 KB Output is correct
2 Correct 13 ms 2516 KB Output is correct
3 Correct 60 ms 5036 KB Output is correct
4 Correct 25 ms 3924 KB Output is correct
5 Correct 14 ms 3308 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2532 KB Output is correct
2 Correct 13 ms 2516 KB Output is correct
3 Correct 60 ms 5036 KB Output is correct
4 Correct 25 ms 3924 KB Output is correct
5 Correct 14 ms 3308 KB Output is correct
6 Correct 9 ms 2260 KB Output is correct
7 Correct 40 ms 4860 KB Output is correct
8 Correct 114 ms 2028 KB Output is correct
9 Correct 75 ms 1996 KB Output is correct
10 Correct 17 ms 2152 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 12 ms 2532 KB Output is correct
7 Correct 13 ms 2516 KB Output is correct
8 Correct 60 ms 5036 KB Output is correct
9 Correct 25 ms 3924 KB Output is correct
10 Correct 14 ms 3308 KB Output is correct
11 Correct 9 ms 2260 KB Output is correct
12 Correct 40 ms 4860 KB Output is correct
13 Correct 114 ms 2028 KB Output is correct
14 Correct 75 ms 1996 KB Output is correct
15 Correct 17 ms 2152 KB Output is correct
16 Correct 26 ms 2952 KB Output is correct
17 Correct 73 ms 3424 KB Output is correct
18 Correct 57 ms 16256 KB Output is correct
19 Correct 117 ms 2016 KB Output is correct
20 Correct 28 ms 2388 KB Output is correct
21 Correct 208 ms 77388 KB Output is correct
22 Correct 97 ms 3792 KB Output is correct
23 Correct 244 ms 2252 KB Output is correct
24 Correct 100 ms 2932 KB Output is correct
25 Correct 260 ms 140424 KB Output is correct