Submission #864084

#	Time	Username	Problem	Language	Result	Execution time	Memory
864084		phoenix0423	Museum (CEOI17_museum)	C++17	100 / 100	470 ms	320520 KiB

museum

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
// #pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 2e5 + 5;
const ll INF = 1e18;

ll n, k, st;
vector<pll> adj[maxn];
vector<ll> dp[maxn][2];

vector<ll> total_min(vector<ll> a, vector<ll> b, int ded = 0){
	vector<ll> nw(a.size() + b.size() - 1, INF);
	for(int i = 0; i < a.size(); i++){
		for(int j = 0; j < b.size(); j++){
			nw[i + j] = min(nw[i + j], a[i] + b[j] - ded);
		}
	}
	return nw;
}

void chgmin(vector<ll> &a, vector<ll> b){
	int sz = max(a.size(), b.size());
	a.resize(sz, INF);
	b.resize(sz, INF);
	for(int i = 0; i < sz; i++) a[i] = min(a[i], b[i]);
}
void dfs(int pos, int prev, int plen){
	dp[pos][0] = {INF, plen};
	dp[pos][1] = {INF, plen * 2};
	for(auto [x, w] : adj[pos]){
		if(x == prev) continue;
		dfs(x, pos, w);
		dp[pos][0] = total_min(dp[pos][0], dp[x][1]);
		chgmin(dp[pos][0], total_min(dp[pos][1], dp[x][0], plen));
		dp[pos][1] = total_min(dp[pos][1], dp[x][1]);
	}
	dp[pos][0][0] = dp[pos][1][0] = 0;
}

int main(void){
	fastio;
	cin>>n>>k>>st;
	st--;
	for(int i = 0; i < n - 1; i++){
		int a, b, c;
		cin>>a>>b>>c;
		a--, b--;
		adj[a].eb(b, c);
		adj[b].eb(a, c);
	}
	dfs(st, -1, 0);
	cout<<min(dp[st][0][k], dp[st][1][k])<<"\n";
}

Compilation message (stderr)

museum.cpp: In function 'std::vector<long long int> total_min(std::vector<long long int>, std::vector<long long int>, int)':
museum.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i = 0; i < a.size(); i++){
      |                 ~~^~~~~~~~~~
museum.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for(int j = 0; j < b.size(); j++){
      |                  ~~^~~~~~~~~~

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