oj.uz

Submission #604237

# Submission time Handle Problem Language Result Execution time Memory
604237 2022-07-24T22:58:45 Z ziduo Museum (CEOI17_museum) C++14
100 / 100
 468 ms 746064 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
int n, k, x, cnt[10001], dp[10001][10001][2];
vector<pair<int, int>> edges[10001];
void subSize(int cur, int par){
    cnt[cur] = 1;
    for(pair<int, int> i:edges[cur] ){
        if(i.f==par)continue;
        subSize(i.f, cur);
        cnt[cur]+=cnt[i.f];
    }
}
void dfs(int cur, int par){
    int currSize=1;
    for(pair<int, int> i: edges[cur]){
        if(i.f==par)continue;
        dfs(i.f, cur);
        for(int j=currSize; j>=1; j--){
            for(int m=cnt[i.f]; m>=1; m--){
                dp[cur][j+m][0]=min(min(dp[cur][j+m][0],dp[cur][j][1]+dp[i.f][m][0]+i.s),dp[cur][j][0]+dp[i.f][m][1]+2*i.s);
                dp[cur][j+m][1]=min(dp[cur][j+m][1],dp[cur][j][1]+dp[i.f][m][1] + 2*i.s);
            }
        }
        currSize+=cnt[i.f];
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    cin>>n>>k>>x;
    x--;
   for(int i=0; i<n-1; i++){
        int a, b, c;
        cin>>a>>b>>c;
        a--;b--;
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    for(int i=0; i<=n; i++)for(int j=2; j<=k; j++)dp[i][j][0]=dp[i][j][1]=1000000000;
    subSize(x, -1);
    dfs(x, -1);
    cout<<dp[x][k][0]<<endl;
}

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 564 KB Output is correct
3 Correct 0 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 141 ms 51376 KB Output is correct
2 Correct 149 ms 51616 KB Output is correct
3 Correct 215 ms 181524 KB Output is correct
4 Correct 162 ms 90736 KB Output is correct
5 Correct 153 ms 59332 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 51376 KB Output is correct
2 Correct 149 ms 51616 KB Output is correct
3 Correct 215 ms 181524 KB Output is correct
4 Correct 162 ms 90736 KB Output is correct
5 Correct 153 ms 59332 KB Output is correct
6 Correct 141 ms 50864 KB Output is correct
7 Correct 237 ms 125972 KB Output is correct
8 Correct 217 ms 50400 KB Output is correct
9 Correct 170 ms 50508 KB Output is correct
10 Correct 142 ms 51008 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Correct 0 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 141 ms 51376 KB Output is correct
7 Correct 149 ms 51616 KB Output is correct
8 Correct 215 ms 181524 KB Output is correct
9 Correct 162 ms 90736 KB Output is correct
10 Correct 153 ms 59332 KB Output is correct
11 Correct 141 ms 50864 KB Output is correct
12 Correct 237 ms 125972 KB Output is correct
13 Correct 217 ms 50400 KB Output is correct
14 Correct 170 ms 50508 KB Output is correct
15 Correct 142 ms 51008 KB Output is correct
16 Correct 172 ms 121844 KB Output is correct
17 Correct 301 ms 433616 KB Output is correct
18 Correct 191 ms 158808 KB Output is correct
19 Correct 208 ms 120800 KB Output is correct
20 Correct 176 ms 121288 KB Output is correct
21 Correct 425 ms 745776 KB Output is correct
22 Correct 424 ms 745620 KB Output is correct
23 Correct 468 ms 745752 KB Output is correct
24 Correct 422 ms 745684 KB Output is correct
25 Correct 430 ms 746064 KB Output is correct