Submission #110856

#	Time	Username	Problem	Language	Result	Execution time	Memory
110856		user202729	Beads and wires (APIO14_beads)	C++17	100 / 100	354 ms	22508 KiB

beads

#include<iostream>
#include<cassert>
#include<vector>
#include<array>
#include<algorithm>
#include<climits>

struct edge{
	int n,w;
};
static std::vector<std::vector<edge>> ad;
static std::vector<int> parw;

static std::vector<int> f0,f1,g0,g1;
// f_rf[i]: max value of subtree rooted at i,
// g_rf[i] = ~ but also include edge from i to parent
// where rf = must the component be done first? (0/1)

static auto const b1=[](edge e){
	int j=e.n;
	return f1[j]+e.w-g0[j];
};
static auto const b2=[](edge e){
	int j=e.n;
	return f0[j]+e.w-g0[j];
};

static auto const compb1=[](edge a,edge b){
	return b1(a)<b1(b);
};
static auto const compb2=[](edge a,edge b){
	return b2(a)<b2(b);
};

static void dfs(int i){
	int sg0=0; // sum of g0[j] for j in child[i]
	int m=INT_MIN; // max cost when use f0 instead of g0 and pair the edge
	int m1=INT_MIN; // max cost when use f**1** instead of g0 and pair the edge

	int mgf=INT_MIN;

	for(edge e:ad[i]){
		int j=e.n,w=e.w;
		// par[j]=i;
		parw[j]=e.w;
		ad[j].erase(
				std::find_if(begin(ad[j]),end(ad[j]),[i](edge e){
					return e.n==i;
					}));
		dfs(j);

		sg0+=g0[j];
		m=std::max(m,f0[j]-g0[j]+w);
		m1=std::max(m1,f1[j]-g0[j]+w);

		mgf=std::max(mgf,g1[j]-g0[j]);
	}

	f0[i]=sg0; // i cannot be the center of any pair

	g0[i]=sg0;
	if(m+parw[i]>0)g0[i]+=m+parw[i];

	f1[i]=sg0; // if i is constructed first

	if(ad[i].size()>=2){ // otherwise, if i is a pair center, one get benefit f1+w-g0 (B1) and another get f0+w-g0 (B2)

		// case 1: best B1 get B1, best B2 (except <) get B2
		auto const& ai=ad[i];
		auto bb1=std::max_element(begin(ai),end(ai),compb1);
		int mb2=INT_MIN;
		if(bb1!=begin(ai))
			mb2=std::max(mb2,
				b2(*std::max_element(begin(ai),bb1,compb2)));
		if(bb1+1!=end(ai))
			mb2=std::max(mb2,
				b2(*std::max_element(bb1+1,end(ai),compb2)));
		f1[i]=std::max(f1[i],sg0+b1(*bb1)+mb2);

		// case 2: best B1 get B2, best B1 of rest get B1
		int mb1r=INT_MIN;
		if(bb1!=begin(ai))
			mb1r=std::max(mb1r,
				b1(*std::max_element(begin(ai),bb1,compb1)));
		if(bb1+1!=end(ai))
			mb1r=std::max(mb1r,
				b1(*std::max_element(bb1+1,end(ai),compb1)));
		f1[i]=std::max(f1[i],sg0+b2(*bb1)+mb1r);
	}

	// otherwise (i is not constructed first and not paired) just add max g1-g0
	f1[i]=std::max(f1[i],sg0+mgf);

	g1[i]=f1[i];
	// in case i is a pair center with one leg upward,
	// the first vertex constructed must be inside the other leg
	g1[i]=std::max(g1[i],sg0+m1+parw[i]);

	assert(f1[i]>=f0[i]);
	assert(g1[i]>=g0[i]);
	assert(g0[i]>=f0[i]);
	assert(g1[i]>=f1[i]);
}

int main(){
	int n;std::cin>>n;
	ad.resize(n);
	for(int _=n-1;_--;){
		int a,b,w;std::cin>>a>>b>>w;--a;--b;
		ad[a].push_back({b,w});
		ad[b].push_back({a,w});
	}
	// par.resize(n);
	parw.resize(n);
	f0.resize(n);
	f1.resize(n);
	g0.resize(n);
	g1.resize(n);
	dfs(0);
	std::cout<<f1[0]<<'\n';
}

/*
5
1 2 10
1 3 40
1 4 15
1 5 20

10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43