Submission #1316608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316608		shtn	Museum (CEOI17_museum)	C++20	0 / 100	1 ms	500 KiB

museum

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
// #ifndef ONLINE_JUDGE
//     #include "00_debug.h"
// #else
//     #define debug(x)
// #endif
#define endl '\n'
#define all(a) a.begin(), a.end()
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
void solve(){
    int n,k,x;
    cin>>n>>k>>x;
    vector<vector<pair<int,int>>>g(n);
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        u--,v--;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    vector<vector<vector<int>>>dp(n);
    vector<int>sz(n);
    vector<int>mx(n);
    function<void(int,int)>dfs1=[&](int node,int parent){
        mx[node]=1;
        for(auto child:g[node]){
            if(child.first==parent)continue;
            dfs1(child.first,node);
            mx[node]+=mx[child.first];
        }
    };
    x--;
    dfs1(x,-1);
    function<void(int,int)>dfs=[&](int node,int parent){
        for(auto child:g[node]){
            if(child.first==parent)continue;
            dfs(child.first,node);
        }
        dp[node]=vector<vector<int>>(mx[node]+1,vector<int>(2,1e9));
        dp[node][1][1]=0;
        dp[node][1][0]=0;
        sz[node]=1;
        for(auto child:g[node]){
            if(child.first==parent)continue;
            auto ndp=dp[node];
            for(int i=0;i<=sz[node];i++){
                if(dp[node][i][1]==1e9)continue;
                for(int j=0;j<=sz[child.first];j++){
                    if(dp[child.first][j][0]!=1e9){
                        ndp[i+j][0]=min(ndp[i+j][0],dp[node][i][1]+dp[child.first][j][0]+child.second);
                    }
                    if(dp[child.first][j][1]!=1e9){
                        ndp[i+j][1]=min(ndp[i+j][1],dp[node][i][1]+dp[child.first][j][1]+2*child.second);
                        ndp[i+j][0]=min(ndp[i+j][0],dp[node][i][1]+dp[child.first][j][1]+child.second);
                        ndp[i+j][0]=min(ndp[i+j][0],dp[node][i][0]+dp[child.first][j][1]+2*child.second);
                    }
                }
            }
            dp[child.first].clear();
            sz[node]+=sz[child.first];
            swap(ndp,dp[node]);
        }
    };
    dfs(x,-1);
    cout<<dp[x][k][0]<<endl;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("Input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        freopen("Error.txt","w",stderr);
    #endif
    int t=1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen("Input.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen("output.txt","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen("Error.txt","w",stderr);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20