Submission #986915

#	Time	Username	Problem	Language	Result	Execution time	Memory
986915		amirhoseinfar1385	Museum (CEOI17_museum)	C++17	100 / 100	306 ms	154180 KiB

museum

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+10;
struct yal{
	int u,v,w;
	int getad(int fu){
		return (u^v^fu);
	}
}alle[maxn];
vector<int>adj[maxn];
int sz[maxn],n,x,k,inf=1e9;
vector<int>dp[maxn],pd[maxn];

void vorod(){
	cin>>n>>k>>x;
	for(int i=0;i<n-1;i++){
		cin>>alle[i].u>>alle[i].v>>alle[i].w;
		adj[alle[i].u].push_back(i);
		adj[alle[i].v].push_back(i);
	}
}

void add(int u,int w){
	for(int i=1;i<(int)dp[u].size();i++){
		dp[u][i]+=w;
		pd[u][i]+=2*w;
	}
}
vector<int>fake,fakea;

void merge(int u,int v){
	int szu=dp[u].size(),szv=dp[v].size();
//	vector<int>fake(szu+szv-1,inf),fakea(szu+szv-1,inf);
	fake.clear();
	fakea.clear();
	fake.resize(szu+szv-1,inf);
	fakea.resize(szu+szv-1,inf);
	for(int i=0;i<szu;i++){
		for(int j=0;j<szv;j++){
			fake[i+j]=min(fake[i+j],dp[u][i]+pd[v][j]);
			fake[i+j]=min(fake[i+j],pd[u][i]+dp[v][j]);
			fakea[i+j]=min(fakea[i+j],pd[u][i]+pd[v][j]);
		}
	}
	dp[u].swap(fake);
	pd[u].swap(fakea);
}

void dfs(int u,int par=-1){
	dp[u].resize(2);
	pd[u].resize(2);
	for(auto x:adj[u]){
		int v=alle[x].getad(u);
		if(v==par){
			continue;
		}
		dfs(v,u);
		add(v,alle[x].w);
		merge(u,v);
	}
//	cout<<"hey: "<<u<<" "<<par<<endl;
//	for(auto x:dp[u]){
//		cout<<x<<" ";
//	}
//	cout<<"\n";
//	for(auto x:pd[u]){
//		cout<<x<<" ";
//	}
//	cout<<"\n";
}

void solve(){
	dfs(x);
}

void khor(){
	cout<<dp[x][k]<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("inp.txt","r",stdin);
	vorod();
	solve();
	khor();
}

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