Submission #1283306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283306		quan606303	Museum (CEOI17_museum)	C++20	100 / 100	413 ms	312248 KiB

museum

/*
* @Author: RMQuan 
* @Date: 2025-10-23 13:22:28 
 * @Last Modified by: RMQuan
 * @Last Modified time: 2025-10-23 14:18:29
*/
/*idea : 



*/
#include <bits/stdc++.h>
bool M1;
#define int long long
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define TASK "TEST"
#define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
using namespace std;
const int MOD=1e9+7;
const int inf=1e18;
const int maxn=1e4+7;
const int LOG=17;
vector<pair<int,int> > adj[maxn];
int n,k,root,h[maxn],depth[maxn];
vector<int> dp[maxn][2];//0 la chx chon duoc dinh bo lai - 1 la da chon dc dinh bo lai
vector<int> Merge(vector<int> &a,vector<int> &b)
{
    vector<int> c(a.size()+b.size()-1,inf);
    for (int i=0;i<a.size();i++)
    {
        for (int j=0;j<b.size();j++)c[i+j]=min(c[i+j],a[i]+b[j]);
    }
    return c;
}
void pre_dfs(int u,int p)
{
    for (auto v:adj[u])
    {
        if (v.fi==p)continue;
        h[v.fi]=h[u]+1;
        depth[v.fi]=depth[u]+v.se;
        pre_dfs(v.fi,u);
    }
}
void dfs_cal(int u,int p,int w)
{
    dp[u][0]={0,0};
    dp[u][1]={0,inf};
    for (auto v:adj[u])
    {
        if (v.fi==p)continue;
        dfs_cal(v.fi,u,v.se);
        vector<int> n1=Merge(dp[u][0],dp[v.fi][1]);
        vector<int> n2=Merge(dp[u][1],dp[v.fi][0]);
        dp[u][0]=Merge(dp[u][0],dp[v.fi][0]);
        dp[u][1].resize(n1.size());
        for (int i=0;i<n1.size();i++)dp[u][1][i]=min(n1[i],n2[i]);
    }
    for (int i=1;i<dp[u][1].size();i++)dp[u][1][i]=min(dp[u][1][i],dp[u][0][i]-depth[u]);
    for (int i=1;i<dp[u][0].size();i++)dp[u][0][i]+=2*w;
    for (int i=1;i<dp[u][1].size();i++)dp[u][1][i]+=2*w;
   
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    file();
    cin>>n>>k>>root;
    for (int i=1;i<n;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        adj[x].push_back({y,w});
        adj[y].push_back({x,w});
    }
    pre_dfs(root,0);
    dfs_cal(root,0,0);
    cout<<dp[root][1][k];
    bool M2;
    cerr<<"-------------------------------------------------"<<endl;
    cerr<<"Time : "<<clock()<<" ms"<<endl;
    cerr<<"Memory : "<<abs(&M2-&M1)/1024/1024<<" MB"<<endl;
    cerr<<"-------------------------------------------------"<<endl;
    return 0;
}

Compilation message (stderr)

museum.cpp: In function 'int32_t main()':
museum.cpp:25:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
museum.cpp:77:5: note: in expansion of macro 'file'
   77 |     file();
      |     ^~~~
museum.cpp:25:81: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:77:5: note: in expansion of macro 'file'
   77 |     file();
      |     ^~~~

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