oj.uz

Submission #341282

# Submission time Handle Problem Language Result Execution time Memory
341282 2020-12-29T10:55:21 Z phathnv Museum (CEOI17_museum) C++11
100 / 100
 843 ms 784884 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 10001;
const int INF = 1e9;

struct Tedge{
    int v, w;
    Tedge(int _v, int _w){
        v = _v;
        w = _w;
    }
};

int n, k, x, dp[N][N][2], sz[N], tmpDp[N][2];
vector <Tedge> adj[N];

void minimize(int &x, const int &y){
    if (x > y)
        x = y;
}

void dfs(int u, int p){
    sz[u] = 1;
    for(int i = 1; i <= n; i++)
        dp[u][i][0] = dp[u][i][1] = INF;
    dp[u][1][0] = dp[u][1][1] = 0;

    for(Tedge e : adj[u]){
        int v = e.v;
        int w = e.w;
        if (v == p)
            continue;
        dfs(v, u);

        for(int i = 1; i <= n; i++){
            tmpDp[i][0] = dp[u][i][0];
            tmpDp[i][1] = dp[u][i][1];
        }
        for(int a = 1; a <= sz[u]; a++)
            for(int b = 1; b <= sz[v]; b++){
                minimize(tmpDp[a + b][0], dp[u][a][1] + dp[v][b][0] + w);
                minimize(tmpDp[a + b][0], dp[u][a][0] + dp[v][b][1] + 2 * w);
                minimize(tmpDp[a + b][1], dp[u][a][1] + dp[v][b][1] + 2 * w);
            }

        sz[u] += sz[v];
        for(int i = 1; i <= n; i++){
            dp[u][i][0] = tmpDp[i][0];
            dp[u][i][1] = tmpDp[i][1];
        }
    }
}

void readInput(){
    cin >> n >> k >> x;
    for(int i = 1; i < n; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(Tedge(v, w));
        adj[v].push_back(Tedge(u, w));
    }
}

void solve(){
    dfs(x, -1);
    cout << dp[x][k][0];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    readInput();
    solve();
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 810 ms 784160 KB Output is correct
2 Correct 804 ms 784108 KB Output is correct
3 Correct 812 ms 784884 KB Output is correct
4 Correct 811 ms 784236 KB Output is correct
5 Correct 804 ms 784236 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 810 ms 784160 KB Output is correct
2 Correct 804 ms 784108 KB Output is correct
3 Correct 812 ms 784884 KB Output is correct
4 Correct 811 ms 784236 KB Output is correct
5 Correct 804 ms 784236 KB Output is correct
6 Correct 802 ms 784108 KB Output is correct
7 Correct 827 ms 784464 KB Output is correct
8 Correct 843 ms 784108 KB Output is correct
9 Correct 825 ms 784108 KB Output is correct
10 Correct 808 ms 784236 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 810 ms 784160 KB Output is correct
7 Correct 804 ms 784108 KB Output is correct
8 Correct 812 ms 784884 KB Output is correct
9 Correct 811 ms 784236 KB Output is correct
10 Correct 804 ms 784236 KB Output is correct
11 Correct 802 ms 784108 KB Output is correct
12 Correct 827 ms 784464 KB Output is correct
13 Correct 843 ms 784108 KB Output is correct
14 Correct 825 ms 784108 KB Output is correct
15 Correct 808 ms 784236 KB Output is correct
16 Correct 805 ms 784364 KB Output is correct
17 Correct 803 ms 784108 KB Output is correct
18 Correct 811 ms 784492 KB Output is correct
19 Correct 827 ms 784108 KB Output is correct
20 Correct 805 ms 784164 KB Output is correct
21 Correct 802 ms 784364 KB Output is correct
22 Correct 802 ms 784236 KB Output is correct
23 Correct 832 ms 784236 KB Output is correct
24 Correct 810 ms 784220 KB Output is correct
25 Correct 805 ms 784780 KB Output is correct