Submission #167944

#	Time	Username	Problem	Language	Result	Execution time	Memory
167944		FieryPhoenix	Museum (CEOI17_museum)	C++11	100 / 100	569 ms	167704 KiB

museum

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

int N,K,X;
vector<pair<int,int>>adj[10001];
int subsize[10001];
vector<int>dp[10001][2]; //min cost , 0 is round trip , 1 is end

void dfs(int node, int par){
  for (auto p:adj[node])
    if (par!=p.first){
      dfs(p.first,node);
      subsize[node]+=subsize[p.first];
    }
  subsize[node]++;
  for (int i=0;i<=subsize[node];i++){
    dp[node][0].push_back(INF);
    dp[node][1].push_back(INF);
  }
  dp[node][0][1]=0;
  dp[node][1][1]=0;
  for (auto p:adj[node])
    if (par!=p.first){
      for (int i=subsize[node]-subsize[p.first];i>=1;i--){
	for (int j=1;j<=subsize[p.first] && i+j<=subsize[node];j++){
	  dp[node][0][i+j]=min(dp[node][0][i+j],dp[node][0][i]+dp[p.first][0][j]+p.second*2);
	  dp[node][1][i+j]=min(dp[node][1][i+j],dp[node][0][i]+dp[p.first][1][j]+p.second);
	  dp[node][1][i+j]=min(dp[node][1][i+j],dp[node][1][i]+dp[p.first][0][j]+p.second*2);
	}
      }
    }
}
	     
int main()
{
  //ios_base::sync_with_stdio(0);cin.tie(0);
  //freopen (".in","r",stdin);
  //freopen (".out","w",stdout);
  cin>>N>>K>>X;
  for (int i=1;i<N;i++){
    int A,B,C;
    cin>>A>>B>>C;
    adj[A].push_back({B,C});
    adj[B].push_back({A,C});
  }
  dfs(X,X);
  cout<<dp[X][1][K]<<endl;
  return 0;
}

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