oj.uz

Submission #1097575

# Submission time Handle Problem Language Result Execution time Memory
1097575 2024-10-07T15:12:44 Z vjudge1 Museum (CEOI17_museum) C++17
80 / 100
 537 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 0 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 0 ms 604 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 50492 KB Output is correct
2 Correct 113 ms 50772 KB Output is correct
3 Correct 173 ms 51284 KB Output is correct
4 Correct 125 ms 50840 KB Output is correct
5 Correct 112 ms 50516 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 50492 KB Output is correct
2 Correct 113 ms 50772 KB Output is correct
3 Correct 173 ms 51284 KB Output is correct
4 Correct 125 ms 50840 KB Output is correct
5 Correct 112 ms 50516 KB Output is correct
6 Correct 119 ms 51024 KB Output is correct
7 Correct 143 ms 51180 KB Output is correct
8 Correct 334 ms 99920 KB Output is correct
9 Correct 238 ms 60752 KB Output is correct
10 Correct 123 ms 51432 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 604 KB Output is correct
6 Correct 107 ms 50492 KB Output is correct
7 Correct 113 ms 50772 KB Output is correct
8 Correct 173 ms 51284 KB Output is correct
9 Correct 125 ms 50840 KB Output is correct
10 Correct 112 ms 50516 KB Output is correct
11 Correct 119 ms 51024 KB Output is correct
12 Correct 143 ms 51180 KB Output is correct
13 Correct 334 ms 99920 KB Output is correct
14 Correct 238 ms 60752 KB Output is correct
15 Correct 123 ms 51432 KB Output is correct
16 Correct 160 ms 120916 KB Output is correct
17 Correct 347 ms 433488 KB Output is correct
18 Correct 179 ms 121172 KB Output is correct
19 Correct 308 ms 180988 KB Output is correct
20 Correct 165 ms 121744 KB Output is correct
21 Correct 506 ms 746364 KB Output is correct
22 Correct 537 ms 746068 KB Output is correct
23 Runtime error 530 ms 1048576 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -