oj.uz

Submission #780446

# Submission time Handle Problem Language Result Execution time Memory
780446 2023-07-12T09:05:14 Z quochuy147 Museum (CEOI17_museum) C++14
100 / 100
 370 ms 140264 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(sz[u] + 2, inf);
    f[u][1].assign(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)
            for(int j = max(0, i - tot + sz[v]); j <= min(i, sz[v]); ++j) {
                if(i - j > tot - sz[v]) continue;
                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 158 ms 3572 KB Output is correct
2 Correct 156 ms 3880 KB Output is correct
3 Correct 317 ms 136784 KB Output is correct
4 Correct 207 ms 44504 KB Output is correct
5 Correct 168 ms 12432 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 3572 KB Output is correct
2 Correct 156 ms 3880 KB Output is correct
3 Correct 317 ms 136784 KB Output is correct
4 Correct 207 ms 44504 KB Output is correct
5 Correct 168 ms 12432 KB Output is correct
6 Correct 165 ms 3032 KB Output is correct
7 Correct 252 ms 80480 KB Output is correct
8 Correct 370 ms 2180 KB Output is correct
9 Correct 289 ms 2344 KB Output is correct
10 Correct 172 ms 2852 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 158 ms 3572 KB Output is correct
7 Correct 156 ms 3880 KB Output is correct
8 Correct 317 ms 136784 KB Output is correct
9 Correct 207 ms 44504 KB Output is correct
10 Correct 168 ms 12432 KB Output is correct
11 Correct 165 ms 3032 KB Output is correct
12 Correct 252 ms 80480 KB Output is correct
13 Correct 370 ms 2180 KB Output is correct
14 Correct 289 ms 2344 KB Output is correct
15 Correct 172 ms 2852 KB Output is correct
16 Correct 156 ms 4252 KB Output is correct
17 Correct 163 ms 4180 KB Output is correct
18 Correct 221 ms 54504 KB Output is correct
19 Correct 315 ms 2252 KB Output is correct
20 Correct 157 ms 3020 KB Output is correct
21 Correct 241 ms 77260 KB Output is correct
22 Correct 155 ms 3820 KB Output is correct
23 Correct 306 ms 2260 KB Output is correct
24 Correct 159 ms 2932 KB Output is correct
25 Correct 314 ms 140264 KB Output is correct