oj.uz

Submission #926599

# Submission time Handle Problem Language Result Execution time Memory
926599 2024-02-13T12:03:33 Z Warinchai Museum (CEOI17_museum) C++14
100 / 100
 426 ms 784976 KB 
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>adj[10005];
int n,k,x;
int inf=1e9;
int dp[2][10005][10005];
int sz[10005];
void dfs(int u,int p=-1){
    //cerr<<u<<"\n";
    sz[u]=1;
    for(auto x:adj[u])if(x.second!=p){
        dfs(x.second,u);
        for(int i=sz[u];i>=0;i--){
            for(int j=sz[x.second];j>=0;j--){
                dp[0][u][i+j]=min(dp[0][u][i+j],dp[0][u][i]+dp[0][x.second][j]+x.first*2);
                dp[1][u][i+j]=min({dp[1][u][i+j],dp[0][u][i]+dp[1][x.second][j]+x.first,dp[1][u][i]+dp[0][x.second][j]+x.first*2});
            }
        }
        sz[u]+=sz[x.second];
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k>>x;
    for(int i=1;i<=n-1;i++){
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back({c,b});
        adj[b].push_back({c,a});
    }
    for(int i=0;i<=n;i++){
        for(int j=2;j<=k;j++){
            dp[0][i][j]=dp[1][i][j]=inf;
        }
    }
    //cerr<<"work\n";
    dfs(x);
    cout<<dp[1][x][k];
}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 557956 KB Output is correct
2 Correct 187 ms 558124 KB Output is correct
3 Correct 262 ms 602200 KB Output is correct
4 Correct 198 ms 573140 KB Output is correct
5 Correct 179 ms 564312 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 557956 KB Output is correct
2 Correct 187 ms 558124 KB Output is correct
3 Correct 262 ms 602200 KB Output is correct
4 Correct 198 ms 573140 KB Output is correct
5 Correct 179 ms 564312 KB Output is correct
6 Correct 169 ms 563244 KB Output is correct
7 Correct 222 ms 588080 KB Output is correct
8 Correct 349 ms 563284 KB Output is correct
9 Correct 284 ms 568656 KB Output is correct
10 Correct 191 ms 567064 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6812 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 333 ms 557956 KB Output is correct
7 Correct 187 ms 558124 KB Output is correct
8 Correct 262 ms 602200 KB Output is correct
9 Correct 198 ms 573140 KB Output is correct
10 Correct 179 ms 564312 KB Output is correct
11 Correct 169 ms 563244 KB Output is correct
12 Correct 222 ms 588080 KB Output is correct
13 Correct 349 ms 563284 KB Output is correct
14 Correct 284 ms 568656 KB Output is correct
15 Correct 191 ms 567064 KB Output is correct
16 Correct 185 ms 589316 KB Output is correct
17 Correct 249 ms 687188 KB Output is correct
18 Correct 218 ms 605464 KB Output is correct
19 Correct 318 ms 592204 KB Output is correct
20 Correct 192 ms 605524 KB Output is correct
21 Correct 353 ms 784960 KB Output is correct
22 Correct 294 ms 784652 KB Output is correct
23 Correct 426 ms 784468 KB Output is correct
24 Correct 299 ms 784616 KB Output is correct
25 Correct 343 ms 784976 KB Output is correct