oj.uz

Submission #780440

# Submission time Handle Problem Language Result Execution time Memory
780440 2023-07-12T09:01:21 Z quochuy147 Museum (CEOI17_museum) C++14
100 / 100
 396 ms 140544 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 + 5;
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] + 5, inf);
    f[u][1].assign(sz[u] + 5, 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()
{
    ios_base::sync_with_stdio(false);
    cin.tie(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 3772 KB Output is correct
2 Correct 162 ms 4076 KB Output is correct
3 Correct 380 ms 136716 KB Output is correct
4 Correct 208 ms 44620 KB Output is correct
5 Correct 195 ms 12584 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 3772 KB Output is correct
2 Correct 162 ms 4076 KB Output is correct
3 Correct 380 ms 136716 KB Output is correct
4 Correct 208 ms 44620 KB Output is correct
5 Correct 195 ms 12584 KB Output is correct
6 Correct 165 ms 3076 KB Output is correct
7 Correct 262 ms 80552 KB Output is correct
8 Correct 396 ms 2224 KB Output is correct
9 Correct 350 ms 2300 KB Output is correct
10 Correct 186 ms 2940 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 3772 KB Output is correct
7 Correct 162 ms 4076 KB Output is correct
8 Correct 380 ms 136716 KB Output is correct
9 Correct 208 ms 44620 KB Output is correct
10 Correct 195 ms 12584 KB Output is correct
11 Correct 165 ms 3076 KB Output is correct
12 Correct 262 ms 80552 KB Output is correct
13 Correct 396 ms 2224 KB Output is correct
14 Correct 350 ms 2300 KB Output is correct
15 Correct 186 ms 2940 KB Output is correct
16 Correct 162 ms 4456 KB Output is correct
17 Correct 164 ms 4200 KB Output is correct
18 Correct 221 ms 54672 KB Output is correct
19 Correct 337 ms 2216 KB Output is correct
20 Correct 166 ms 3020 KB Output is correct
21 Correct 247 ms 77472 KB Output is correct
22 Correct 169 ms 4036 KB Output is correct
23 Correct 304 ms 2272 KB Output is correct
24 Correct 162 ms 3068 KB Output is correct
25 Correct 322 ms 140544 KB Output is correct