oj.uz

Submission #988690

# Submission time Handle Problem Language Result Execution time Memory
988690 2024-05-25T14:34:25 Z LOLOLO Museum (CEOI17_museum) C++17
80 / 100
 3000 ms 785752 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[N][N][2], 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[u][0][1] = dp[u][1][0] = dp[u][0][0] = dp[u][1][1] = 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 <= min(sz[x.f], a); b++) {
                minimize(dp[u][a][0], dp[x.f][b][0] + dp[u][a - b][0] + x.s * 2);
                minimize(dp[u][a][1], dp[x.f][b][1] + dp[u][a - b][0] + x.s);
                minimize(dp[u][a][1], dp[x.f][b][0] + dp[u][a - b][1] + 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[x][k][1], dp[x][k][0]) << '\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 380 ms 784856 KB Output is correct
2 Correct 456 ms 784888 KB Output is correct
3 Correct 266 ms 785056 KB Output is correct
4 Correct 272 ms 785044 KB Output is correct
5 Correct 263 ms 784976 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 785492 KB Output is correct
2 Correct 296 ms 785436 KB Output is correct
3 Correct 301 ms 785752 KB Output is correct
4 Correct 299 ms 785524 KB Output is correct
5 Correct 292 ms 785488 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 785492 KB Output is correct
2 Correct 296 ms 785436 KB Output is correct
3 Correct 301 ms 785752 KB Output is correct
4 Correct 299 ms 785524 KB Output is correct
5 Correct 292 ms 785488 KB Output is correct
6 Correct 367 ms 785424 KB Output is correct
7 Correct 312 ms 785484 KB Output is correct
8 Correct 277 ms 785232 KB Output is correct
9 Correct 261 ms 785300 KB Output is correct
10 Correct 274 ms 785232 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 784856 KB Output is correct
2 Correct 456 ms 784888 KB Output is correct
3 Correct 266 ms 785056 KB Output is correct
4 Correct 272 ms 785044 KB Output is correct
5 Correct 263 ms 784976 KB Output is correct
6 Correct 445 ms 785492 KB Output is correct
7 Correct 296 ms 785436 KB Output is correct
8 Correct 301 ms 785752 KB Output is correct
9 Correct 299 ms 785524 KB Output is correct
10 Correct 292 ms 785488 KB Output is correct
11 Correct 367 ms 785424 KB Output is correct
12 Correct 312 ms 785484 KB Output is correct
13 Correct 277 ms 785232 KB Output is correct
14 Correct 261 ms 785300 KB Output is correct
15 Correct 274 ms 785232 KB Output is correct
16 Correct 332 ms 785488 KB Output is correct
17 Correct 719 ms 785460 KB Output is correct
18 Correct 1690 ms 785576 KB Output is correct
19 Correct 302 ms 785616 KB Output is correct
20 Correct 305 ms 785368 KB Output is correct
21 Execution timed out 3091 ms 785492 KB Time limit exceeded
22 Halted 0 ms 0 KB -