Submission #223965

#	Time	Username	Problem	Language	Result	Execution time	Memory
223965		NaimSS	Museum (CEOI17_museum)	C++14	100 / 100	637 ms	211320 KiB

museum

#include <bits/stdc++.h>
//#define int long long
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define ff first
#define ss second
#define rep(i,l,r) for(int i = (int)l;i<(int)r;i++)
#define td(v) v.begin(),v.end()
//#define M   1000000007 // 1e9 + 7
#define MAXN 200100
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
inline int mod(int n, int m){ int ret = n%m; if(ret < 0) ret += m; return ret; }
int gcd(int a, int b){return (b == 0 ? a : gcd(b, a%b));}
int exp(int a,int b,int m){
    
    if(b==0) return 1;
    if(b==1) return mod(a,m);
    int k = mod(exp(a,b/2,m),m);
    if(b&1){
        return mod(a*mod(k*k,m),m);
    }
    else return mod(k*k,m);
}

int n,k,x;
const int N = 1e4 + 2;
vector<pii> g[N];
int sz[N];
const int MAXK = 1e4 + 2;
vector<int> dp[N][3];
int aux[N][3];
int vis[N];
void dfs(int v,int p=-1){
    sz[v] = 1;
    for(auto to : g[v]){
        if(to.ff==p)continue;
        dfs(to.ff,v);
        sz[v]+=sz[to.ff];
    }
}

void solve(int v,int p=-1,int ar=0){
    if(vis[v]==1LL)return;
    vis[v] = 1LL;
    sz[v] = 1;
    dp[v][0][0] = 0;
    dp[v][0][1] = 2*ar; // sobe
    dp[v][1][1] = ar; // fica mas nao escolhi
    dp[v][2][1] = ar; // ja escolhi onde descer

    for(auto nx : g[v]){
        int to = nx.ff;
        if(to==p)continue;
        solve(to,v,nx.ss);
        rep(i,0,sz[v] + sz[to]+  1)aux[i][0]= aux[i][1] =aux[i][2] = 1e9;
       
        for(int i=1;i<=sz[v];i++){ 
            for(int j=0;j<=sz[to];j++){
          
                aux[i+j][0] = min(aux[i+j][0],dp[v][0][i] + dp[to][0][j]);
                // os dois sobem ^ 
                aux[i+j][1] = min(aux[i+j][1],dp[v][1][i] + dp[to][0][j]);
                // nao escolhi ^ 
                aux[i+j][2] = min(aux[i+j][2],dp[v][1][i] + dp[to][2][j]);
                // escolho descer em to ^
                aux[i+j][2] = min(aux[i+j][2],dp[v][2][i] + dp[to][0][j]);
                // ja escolhi e nao é em to ^
            }
        }
     

        for(int i=0;i<=sz[v]+sz[to];i++){

            dp[v][1][i] = min(dp[v][1][i],aux[i][1]);
            dp[v][0][i] = min(dp[v][0][i],aux[i][0]);
            dp[v][2][i] = min(dp[v][2][i],aux[i][2]);
        }

        sz[v]+=sz[to];


    }


}

int32_t main(){
   
    fastio;
    cin>>n>>k>>x;
    for(int i=0;i<n-1;i++){
        int a,b,c;
        cin>>a>>b>>c;
        g[a].pb(pii(b,c));
        g[b].pb(pii(a,c));
    }
    
    dfs(x);
    
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++){
            dp[i][j].resize(sz[i]+ 10);
            rep(KKK,0,sz[i] + 10)dp[i][j][KKK] = 1e9 + 10;
        }
    }
    for(int i=1;i<=n;i++)sz[i] = 0;
    solve(x);

    cout<<min({dp[x][0][k],dp[x][1][k],dp[x][2][k]})<<endl;

}

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