oj.uz

Submission #988681

# Submission time Handle Problem Language Result Execution time Memory
988681 2024-05-25T14:26:32 Z LOLOLO Museum (CEOI17_museum) C++17
80 / 100
 3000 ms 785892 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    (ll)__builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 1e4 + 10;
int dp[2][N][N], sz[N];
vector <pair <int, int>> ed[N];
int n, k;

void minimize(int &a, int b) {
    if (a > b) {
        a = b;
    }
}

void dfs(int u, int v) {
    sz[u] = 1;
    dp[0][u][1] = dp[1][u][1] = dp[0][u][0] = dp[1][u][0] = 0;
    for (auto x : ed[u]) {
        if (x.f == v)
            continue;

        dfs(x.f, u);
        for (int a = min(k, sz[u] + sz[x.f]); a >= 1; a--) {
            for (int b = 0; b <= a; b++) {
                minimize(dp[0][u][a], dp[0][x.f][b] + dp[0][u][a - b] + x.s * 2);
                minimize(dp[1][u][a], dp[1][x.f][b] + dp[0][u][a - b] + x.s);
                minimize(dp[1][u][a], dp[0][x.f][b] + dp[1][u][a - b] + x.s * 2);
            }
        }

        sz[u] += sz[x.f];
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    mem(dp, 0x3f);
    int x;
    cin >> n >> k >> x;

    for (int i = 1; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        ed[a].pb({b, c});
        ed[b].pb({a, c});
    }

    dfs(x, x);

    cout << min(dp[0][x][k], dp[1][x][k]) << '\n';
    return 0;
}

/*
11 8 3
1 3 3
3 2 5
6 4 5
1 11 3
9 1 2
9 10 2
3 7 10
6 7 1
7 8 1
7 5 1
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 784800 KB Output is correct
2 Correct 282 ms 784976 KB Output is correct
3 Correct 282 ms 784980 KB Output is correct
4 Correct 272 ms 784976 KB Output is correct
5 Correct 271 ms 785156 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 785492 KB Output is correct
2 Correct 300 ms 785348 KB Output is correct
3 Correct 322 ms 785892 KB Output is correct
4 Correct 329 ms 785420 KB Output is correct
5 Correct 278 ms 785232 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 785492 KB Output is correct
2 Correct 300 ms 785348 KB Output is correct
3 Correct 322 ms 785892 KB Output is correct
4 Correct 329 ms 785420 KB Output is correct
5 Correct 278 ms 785232 KB Output is correct
6 Correct 283 ms 785236 KB Output is correct
7 Correct 332 ms 785564 KB Output is correct
8 Correct 368 ms 785424 KB Output is correct
9 Correct 363 ms 785232 KB Output is correct
10 Correct 325 ms 785232 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 784800 KB Output is correct
2 Correct 282 ms 784976 KB Output is correct
3 Correct 282 ms 784980 KB Output is correct
4 Correct 272 ms 784976 KB Output is correct
5 Correct 271 ms 785156 KB Output is correct
6 Correct 278 ms 785492 KB Output is correct
7 Correct 300 ms 785348 KB Output is correct
8 Correct 322 ms 785892 KB Output is correct
9 Correct 329 ms 785420 KB Output is correct
10 Correct 278 ms 785232 KB Output is correct
11 Correct 283 ms 785236 KB Output is correct
12 Correct 332 ms 785564 KB Output is correct
13 Correct 368 ms 785424 KB Output is correct
14 Correct 363 ms 785232 KB Output is correct
15 Correct 325 ms 785232 KB Output is correct
16 Correct 360 ms 785224 KB Output is correct
17 Correct 934 ms 785608 KB Output is correct
18 Correct 2151 ms 785696 KB Output is correct
19 Execution timed out 3055 ms 785488 KB Time limit exceeded
20 Halted 0 ms 0 KB -