oj.uz

Submission #988674

# Submission time Handle Problem Language Result Execution time Memory
988674 2024-05-25T13:45:46 Z LOLOLO Museum (CEOI17_museum) C++17
80 / 100
 3000 ms 17512 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;
ll dp[2][N][101];
vector <pair <ll, ll>> ed[N];
int n, k;

void minimize(ll &a, ll 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 4 ms 16476 KB Output is correct
2 Correct 4 ms 16472 KB Output is correct
3 Correct 4 ms 16476 KB Output is correct
4 Correct 5 ms 16476 KB Output is correct
5 Correct 4 ms 16264 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 16984 KB Output is correct
2 Correct 107 ms 17224 KB Output is correct
3 Correct 103 ms 17476 KB Output is correct
4 Correct 107 ms 17512 KB Output is correct
5 Correct 101 ms 17224 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 16984 KB Output is correct
2 Correct 107 ms 17224 KB Output is correct
3 Correct 103 ms 17476 KB Output is correct
4 Correct 107 ms 17512 KB Output is correct
5 Correct 101 ms 17224 KB Output is correct
6 Correct 99 ms 16988 KB Output is correct
7 Correct 116 ms 17364 KB Output is correct
8 Correct 102 ms 17108 KB Output is correct
9 Correct 100 ms 16988 KB Output is correct
10 Correct 131 ms 16984 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16476 KB Output is correct
2 Correct 4 ms 16472 KB Output is correct
3 Correct 4 ms 16476 KB Output is correct
4 Correct 5 ms 16476 KB Output is correct
5 Correct 4 ms 16264 KB Output is correct
6 Correct 101 ms 16984 KB Output is correct
7 Correct 107 ms 17224 KB Output is correct
8 Correct 103 ms 17476 KB Output is correct
9 Correct 107 ms 17512 KB Output is correct
10 Correct 101 ms 17224 KB Output is correct
11 Correct 99 ms 16988 KB Output is correct
12 Correct 116 ms 17364 KB Output is correct
13 Correct 102 ms 17108 KB Output is correct
14 Correct 100 ms 16988 KB Output is correct
15 Correct 131 ms 16984 KB Output is correct
16 Execution timed out 3027 ms 16988 KB Time limit exceeded
17 Halted 0 ms 0 KB -