Submission #1284744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284744		quan606303	Museum (CEOI17_museum)	C++20	20 / 100	3098 ms	51840 KiB

museum

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



*/
#include <bits/stdc++.h>
bool M1;
#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=1e9;
const int maxn=1e4+7;
const int LOG=17;
vector<pair<int,int> > adj[maxn];
int n,k,root;
int pos[maxn],h[maxn],depth[maxn],id_rmq=0,rmq[2*maxn][LOG+1];
void dfs(int u,int p)
{
    pos[u]=++id_rmq;
    rmq[id_rmq][0]=u;
    for (auto v:adj[u])
    {
        if (v.fi==p)continue;
        h[v.fi]=h[u]+1;
        depth[v.fi]=depth[u]+v.se;
        dfs(v.fi,u);
        rmq[++id_rmq][0]=u;
    }
}
int get_min_h(int u,int v)
{
    return (h[u]<h[v]?u:v);
}
int lca(int u,int v)
{
    int L=pos[u];
    int R=pos[v];
    if (L>R)swap(L,R);
    int k=__lg(R-L+1);
    return get_min_h(rmq[L][k],rmq[R-(1<<k)+1][k]);
}
int dist(int u,int v)
{
    return depth[u]+depth[v]-2*depth[lca(u,v)];
}
void prepare_lca()
{
    for (int j=1;j<=LOG;j++)
    {
        for (int i=1;i+(1<<j)-1<=id_rmq;i++)rmq[i][j]=get_min_h(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
    }
}
bool cmp(int u,int v)
{
    return pos[u]<pos[v];
}
int dp[maxn][maxn][2];
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});
    }
    vector<int> node;
    dfs(root,0);
    prepare_lca();
    for (int i=1;i<=n;i++)node.push_back(i);
    sort(node.begin(),node.end(),cmp);
    for (int i=0;i<=n;i++)
    {
        for (int j=0;j<=k;j++)dp[i][j][0]=dp[i][j][1]=inf;
    }
    dp[0][1][0]=0;
    dp[0][1][1]=-depth[root];
    for (int j=2;j<=k;j++)
    {
        for (int u=j-1;u<n;u++)
        {
            for (int v=u-1;v>=0;v--)
            {
                dp[u][j][0]=min(dp[u][j][0],dp[v][j-1][0]+dist(node[v],node[u]));
                dp[u][j][1]=min({dp[u][j][1],dp[v][j-1][1]+dist(node[v],node[u]),dp[v][j-1][0]+dist(node[v],node[u])-depth[node[u]]});
            }
        }
    }
    int ans=inf;
    for (int i=0;i<n;i++)ans=min(ans,min(dp[i][k][0],dp[i][k][1])+dist(node[i],root));
    cout<<ans;
    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:24:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
museum.cpp:79:5: note: in expansion of macro 'file'
   79 |     file();
      |     ^~~~
museum.cpp:24:81: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:79:5: note: in expansion of macro 'file'
   79 |     file();
      |     ^~~~

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