oj.uz

Submission #1097568

# Submission time Handle Problem Language Result Execution time Memory
1097568 2024-10-07T15:07:16 Z vjudge1 Museum (CEOI17_museum) C++17
80 / 100
 534 ms 1048576 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e4 + 7;
const ll oo = (ll) 1e9 + 69;

int n, k, x, u, v, w, sz[maxn], dp[maxn][maxn][2], f[maxn][maxn][2];
vector<pa> g[maxn];

void dfs(int u, int par) {
    for(auto e:g[u]) {
        int v = e.fi;
        if(v == par) continue;
        dfs(v, u);
    }

    for(int i = 0; i <= Size(g[u]); i++) {
        for(int j = 0; j <= k; j++) {
            for(int t = 0; t < 2; t++) {
                f[i][j][t] = oo;
            }
        }
    }
    f[0][1][1] = 0;
    f[0][1][0] = 0;
    // f[0][0][0] = 0;
    // f[0][0][1] = 0;
    sz[u] = 1;

    for(int i = 1; i <= Size(g[u]); i++) {
        int v = g[u][i - 1].fi;
        int w = g[u][i - 1].se;
        if(v == par) {
            for(int j = 0; j <= sz[u]; j++) {
                for(int t = 0; t < 2; t++) {
                    f[i][j][t] = f[i - 1][j][t];
                }
            }
            continue;
        }

        for(int j = 0; j <= sz[u]; j++) {
            for(int pre = 0; pre <= sz[v]; pre++) {
                int cost = w * (pre > 0);
                mini(f[i][j + pre][0], f[i - 1][j][0] + dp[v][pre][1] + 2 * cost);
                mini(f[i][j + pre][0], f[i - 1][j][1] + dp[v][pre][0] + cost);
                mini(f[i][j + pre][1], f[i - 1][j][1] + dp[v][pre][1] + 2 * cost);
            }
        }
        sz[u] += sz[v];
    }

    for(int i = 0; i <= k; i++) {
        for(int t = 0; t < 2; t++) {
            dp[u][i][t] = f[Size(g[u])][i][t];
        }
    }
    dp[u][0][0] = dp[u][0][1] = 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>k>>x;
    for(int i = 1; i < n; i++) {
        cin>>u>>v>>w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    dfs(x, 0);
    cout<<min(dp[x][k][0], dp[x][k][1]);
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 700 KB Output is correct
5 Correct 0 ms 604 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 50516 KB Output is correct
2 Correct 128 ms 50772 KB Output is correct
3 Correct 171 ms 51148 KB Output is correct
4 Correct 129 ms 50768 KB Output is correct
5 Correct 114 ms 50516 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 50516 KB Output is correct
2 Correct 128 ms 50772 KB Output is correct
3 Correct 171 ms 51148 KB Output is correct
4 Correct 129 ms 50768 KB Output is correct
5 Correct 114 ms 50516 KB Output is correct
6 Correct 113 ms 50812 KB Output is correct
7 Correct 150 ms 51116 KB Output is correct
8 Correct 358 ms 99928 KB Output is correct
9 Correct 282 ms 60756 KB Output is correct
10 Correct 124 ms 51448 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 700 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 112 ms 50516 KB Output is correct
7 Correct 128 ms 50772 KB Output is correct
8 Correct 171 ms 51148 KB Output is correct
9 Correct 129 ms 50768 KB Output is correct
10 Correct 114 ms 50516 KB Output is correct
11 Correct 113 ms 50812 KB Output is correct
12 Correct 150 ms 51116 KB Output is correct
13 Correct 358 ms 99928 KB Output is correct
14 Correct 282 ms 60756 KB Output is correct
15 Correct 124 ms 51448 KB Output is correct
16 Correct 156 ms 120916 KB Output is correct
17 Correct 324 ms 433484 KB Output is correct
18 Correct 176 ms 121172 KB Output is correct
19 Correct 308 ms 181184 KB Output is correct
20 Correct 157 ms 121684 KB Output is correct
21 Correct 531 ms 746556 KB Output is correct
22 Correct 510 ms 746224 KB Output is correct
23 Runtime error 534 ms 1048576 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -