oj.uz

Submission #988676

# Submission time Handle Problem Language Result Execution time Memory
988676 2024-05-25T13:55:12 Z LOLOLO Museum (CEOI17_museum) C++17
80 / 100
 3000 ms 785664 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];
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) {
    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 = k; 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);
            }
        }
    }
}

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 785016 KB Output is correct
2 Correct 267 ms 784976 KB Output is correct
3 Correct 261 ms 784976 KB Output is correct
4 Correct 371 ms 784976 KB Output is correct
5 Correct 279 ms 784848 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 785416 KB Output is correct
2 Correct 359 ms 785348 KB Output is correct
3 Correct 342 ms 785632 KB Output is correct
4 Correct 347 ms 785664 KB Output is correct
5 Correct 355 ms 785232 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 785416 KB Output is correct
2 Correct 359 ms 785348 KB Output is correct
3 Correct 342 ms 785632 KB Output is correct
4 Correct 347 ms 785664 KB Output is correct
5 Correct 355 ms 785232 KB Output is correct
6 Correct 364 ms 785496 KB Output is correct
7 Correct 373 ms 785472 KB Output is correct
8 Correct 347 ms 785352 KB Output is correct
9 Correct 355 ms 785240 KB Output is correct
10 Correct 355 ms 785236 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 785016 KB Output is correct
2 Correct 267 ms 784976 KB Output is correct
3 Correct 261 ms 784976 KB Output is correct
4 Correct 371 ms 784976 KB Output is correct
5 Correct 279 ms 784848 KB Output is correct
6 Correct 368 ms 785416 KB Output is correct
7 Correct 359 ms 785348 KB Output is correct
8 Correct 342 ms 785632 KB Output is correct
9 Correct 347 ms 785664 KB Output is correct
10 Correct 355 ms 785232 KB Output is correct
11 Correct 364 ms 785496 KB Output is correct
12 Correct 373 ms 785472 KB Output is correct
13 Correct 347 ms 785352 KB Output is correct
14 Correct 355 ms 785240 KB Output is correct
15 Correct 355 ms 785236 KB Output is correct
16 Execution timed out 3049 ms 785180 KB Time limit exceeded
17 Halted 0 ms 0 KB -