oj.uz

Submission #1097578

# Submission time Handle Problem Language Result Execution time Memory
1097578 2024-10-07T15:13:18 Z vjudge1 Museum (CEOI17_museum) C++17
80 / 100
 520 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;
    dp[u][1][0] = 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 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 50352 KB Output is correct
2 Correct 117 ms 50768 KB Output is correct
3 Correct 182 ms 51024 KB Output is correct
4 Correct 133 ms 50688 KB Output is correct
5 Correct 115 ms 50512 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 50352 KB Output is correct
2 Correct 117 ms 50768 KB Output is correct
3 Correct 182 ms 51024 KB Output is correct
4 Correct 133 ms 50688 KB Output is correct
5 Correct 115 ms 50512 KB Output is correct
6 Correct 119 ms 50772 KB Output is correct
7 Correct 155 ms 50928 KB Output is correct
8 Correct 367 ms 99804 KB Output is correct
9 Correct 278 ms 60500 KB Output is correct
10 Correct 123 ms 51292 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 107 ms 50352 KB Output is correct
7 Correct 117 ms 50768 KB Output is correct
8 Correct 182 ms 51024 KB Output is correct
9 Correct 133 ms 50688 KB Output is correct
10 Correct 115 ms 50512 KB Output is correct
11 Correct 119 ms 50772 KB Output is correct
12 Correct 155 ms 50928 KB Output is correct
13 Correct 367 ms 99804 KB Output is correct
14 Correct 278 ms 60500 KB Output is correct
15 Correct 123 ms 51292 KB Output is correct
16 Correct 154 ms 120916 KB Output is correct
17 Correct 334 ms 433488 KB Output is correct
18 Correct 179 ms 121172 KB Output is correct
19 Correct 296 ms 180968 KB Output is correct
20 Correct 152 ms 121712 KB Output is correct
21 Correct 519 ms 746308 KB Output is correct
22 Correct 485 ms 746068 KB Output is correct
23 Runtime error 520 ms 1048576 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -