oj.uz

Submission #826501

# Submission time Handle Problem Language Result Execution time Memory
826501 2023-08-15T16:03:01 Z hafo Museum (CEOI17_museum) C++14
45 / 100
 794 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 = 1e9 + 69;

int n, u, v, w, sz[maxn], dp[maxn][maxn][2], f[maxn][maxn][2], k, node;
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 <= n; j++) 
            for(int en = 0; en < 2; en++) f[i][j][en] = oo;
    f[0][1][1] = 0;
    f[0][1][0] = 0;
    f[0][0][1] = 0;
    f[0][0][0] = 0;
    sz[u] = 1;

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

        for(int j = 0; j <= sz[u]; j++) {
            for(int pre = 0; pre <= sz[v]; pre++) {
                int cost = w;
                if(pre == 0) cost = 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 <= n; i++) 
        for(int en = 0; en < 2; en++) dp[u][i][en] = f[Size(g[u])][i][en];
}

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

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

    cin>>n>>k>>node;
    for(int i = 1; i < n; i++) {
        cin>>u>>v>>w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }

    dfs(node, 0);
    cout<<dp[node][k][0];
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 644 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 794 ms 784728 KB Output is correct
2 Correct 701 ms 784724 KB Output is correct
3 Correct 752 ms 785184 KB Output is correct
4 Correct 687 ms 784832 KB Output is correct
5 Correct 664 ms 784788 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 794 ms 784728 KB Output is correct
2 Correct 701 ms 784724 KB Output is correct
3 Correct 752 ms 785184 KB Output is correct
4 Correct 687 ms 784832 KB Output is correct
5 Correct 664 ms 784788 KB Output is correct
6 Correct 679 ms 785576 KB Output is correct
7 Correct 699 ms 785264 KB Output is correct
8 Runtime error 588 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 644 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 794 ms 784728 KB Output is correct
7 Correct 701 ms 784724 KB Output is correct
8 Correct 752 ms 785184 KB Output is correct
9 Correct 687 ms 784832 KB Output is correct
10 Correct 664 ms 784788 KB Output is correct
11 Correct 679 ms 785576 KB Output is correct
12 Correct 699 ms 785264 KB Output is correct
13 Runtime error 588 ms 1048576 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -