oj.uz

Submission #988683

# Submission time Handle Problem Language Result Execution time Memory
988683 2024-05-25T14:27:42 Z LOLOLO Museum (CEOI17_museum) C++17
80 / 100
 3000 ms 785748 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 <= min(sz[x.f], 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 269 ms 784880 KB Output is correct
2 Correct 283 ms 785104 KB Output is correct
3 Correct 272 ms 784824 KB Output is correct
4 Correct 274 ms 784996 KB Output is correct
5 Correct 270 ms 784836 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 785228 KB Output is correct
2 Correct 287 ms 785400 KB Output is correct
3 Correct 313 ms 785732 KB Output is correct
4 Correct 301 ms 785488 KB Output is correct
5 Correct 303 ms 785424 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 785228 KB Output is correct
2 Correct 287 ms 785400 KB Output is correct
3 Correct 313 ms 785732 KB Output is correct
4 Correct 301 ms 785488 KB Output is correct
5 Correct 303 ms 785424 KB Output is correct
6 Correct 289 ms 785216 KB Output is correct
7 Correct 311 ms 785444 KB Output is correct
8 Correct 292 ms 785288 KB Output is correct
9 Correct 281 ms 785300 KB Output is correct
10 Correct 307 ms 785436 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 784880 KB Output is correct
2 Correct 283 ms 785104 KB Output is correct
3 Correct 272 ms 784824 KB Output is correct
4 Correct 274 ms 784996 KB Output is correct
5 Correct 270 ms 784836 KB Output is correct
6 Correct 287 ms 785228 KB Output is correct
7 Correct 287 ms 785400 KB Output is correct
8 Correct 313 ms 785732 KB Output is correct
9 Correct 301 ms 785488 KB Output is correct
10 Correct 303 ms 785424 KB Output is correct
11 Correct 289 ms 785216 KB Output is correct
12 Correct 311 ms 785444 KB Output is correct
13 Correct 292 ms 785288 KB Output is correct
14 Correct 281 ms 785300 KB Output is correct
15 Correct 307 ms 785436 KB Output is correct
16 Correct 331 ms 785436 KB Output is correct
17 Correct 731 ms 785460 KB Output is correct
18 Correct 1654 ms 785584 KB Output is correct
19 Correct 305 ms 785492 KB Output is correct
20 Correct 314 ms 785432 KB Output is correct
21 Execution timed out 3081 ms 785748 KB Time limit exceeded
22 Halted 0 ms 0 KB -