Submission #1248054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248054		quocbaoo	Museum (CEOI17_museum)	C++20	0 / 100	145 ms	45960 KiB

museum

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int N=1e4,INF=5e8+9;
int n,dp[N+5][N+5],f[N+5];
int bd[N+5],nex[N+5],par[N+5],cnt=0,ke[N+5];
vector<pair<int,int>> g[N+5];
void dfs(int u,int pa){
    cnt++;bd[cnt]=u;
    for (auto j:g[u]){
        if (j.fi==pa) continue;
        if (ke[u]==0) ke[u]=j.fi;
        par[j.fi]=u;f[j.fi]=f[u]+j.se;
        dfs(j.fi,u);
    }
    nex[u]=cnt+1;
}
int get(int u,int v,int pa){
    return f[u]+f[v]-2*f[pa];
}
int ff(int u,int k){
//    cout<<u<<" "<<k<<endl;
    if (k<0) return INF;
    if (u>n) {
        if (k==0) return 0;return INF;
    }
    if (dp[u][k]!=INF) return dp[u][k];
    int ans=INF;
    if (ke[u]!=0) ans=min(ans,ff(ke[u],k-1)+get(u,ke[u],u));
    int z=bd[nex[u]];
    if (z<=n){
        ans=min(ans,ff(z,k)+get(par[u],z,par[z])-get(u,par[u],par[u]));
        ans=min(ans,ff(z,k-1)+get(u,z,par[z]));
        ans=min(ans,ff(n+1,k));
    }
    else ans=min(ans,ff(z,k));
//    cout<<u<<" "<<k<<" "<<ke[u]<<" "<<ans<<endl;
    return dp[u][k]=ans;
}
int main(){
    if (fopen("museum.inp","r")){
        freopen("museum.inp","r",stdin);
        freopen("museum.out","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    int k,x;cin>>k>>x;
    for (int i=1;i<n;i++){
        int u,v,w;cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    bd[n+1]=n+1;
    dfs(x,x);
    for (int i=1;i<=n;i++){
        for (int j=0;j<=k;j++) dp[i][j]=INF;
    }
    //    cout<<get()<<endl;
    cout<<ff(x,k-1);
}

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen("museum.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen("museum.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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