Submission #1277494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277494		tanzim_bn	Museum (CEOI17_museum)	C++20	0 / 100	14 ms	2692 KiB

museum

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

// typedefs...
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update>pref_trie;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;

// constants...
const double PI = acos(-1);
const ll mod = 1e9 + 7; // 998244353
const int MXS = 2e5+5;
const ll MXI = 1e9+5;
const ll MXL = 1e18+5;
const ll INF = 1e9+5;
const ll INFLL = 1e18+5;
const ll EPS = 1e-9;

// defines...
#define MP        make_pair
#define PB        push_back
#define fi         first
#define se         second
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define boost_      ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'

// functions...
ll gcd(ll a, ll b){ while (b){ a %= b; swap(a, b);} return a;}
ll lcm(ll a, ll b){ return (a/gcd(a, b)*b);}
ll ncr(ll a, ll b){ ll x = max(a-b, b), ans=1; for(ll K=a, L=1; K>=x+1; K--, L++){ ans = ans * K; ans /= L;} return ans;}
ll bigmod(ll a,ll b,ll mod){ if(b==0){ return 1;} ll tm=bigmod(a,b/2,mod); tm=(tm*tm)%mod; if(b%2==1) tm=(tm*a)%mod; return tm;}
ll egcd(ll a,ll b,ll &x,ll &y){ if(a==0){ x=0; y=1; return b;} ll x1,y1; ll d=egcd(b%a,a,x1,y1); x=y1-(b/a)*x1; y=x1; return d;}
ll modpow(ll a,ll p,ll mod) {ll ans=1;while(p){if(p%2)ans=(ans*a)%mod;a=(a*a)%mod;p/=2;} return ans;}
ll inverse_mod(ll n,ll mod) {return modpow(n,mod-2,mod);}

vector<pii> v[10005];
vector<int> dp[10001][2];
int n, k, st;

int check(int pos, int pre, int rd) {

   dp[pos][0].PB(0);
   dp[pos][1].PB(0);
   int sz = 0;
   for(auto it : v[pos]) {
      if(it.fi == pre) continue;
      sz += check(it.fi, pos, it.se);
   }

   for(int i = 1; i <= min(sz, k - 1); i++) {
      dp[pos][0].PB(INF);
      dp[pos][1].PB(INF);
   }

   for(auto it : v[pos]) {
      if(it.fi == pre) continue;
      // cout << pos << "--" << it.fi << endl;
      for(int i = min(sz, k - 1); i >= 1; i--) {
         // overall i + 1 nodes
         for(int j = 0; j < dp[it.fi][0].size(); j++) {
            // taking j + 1 nodes
            if(j >= i) continue;
            // cout << i << j + 1 << endl;
            // cout << i - j - 1 << endl;
            dp[pos][0][i] = min(dp[pos][0][i], dp[it.fi][0][j] + dp[pos][0][i - j - 1] + 2 * it.se);
            dp[pos][1][i] = min(dp[pos][1][i], dp[it.fi][1][j] + dp[pos][0][i - j - 1] + it.se);
         }
      }
   }


   return sz + 1;

}

void solve() {
   
   cin >> n >> k >> st;

   for(int i = 1; i < n; i++) {
      int x, y, c;
      cin >> x >> y >> c;
      v[x].PB({y, c});
      v[y].PB({x, c});
   }

   check(st, st, 0);
   cout << dp[st][1][k-1] << endl;
   
}   
int main()
{
    boost_;
    int t=1;
     // cin>>t;
    for(int i=1;i<=t;i++)
    {
       // cout<<"Case "<<i<<": ";
       solve();
    }
}
/*

1 3
0 2

*/

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