Submission #110829

#	Time	Username	Problem	Language	Result	Execution time	Memory
110829		user202729	구슬과 끈 (APIO14_beads)	C++17	0 / 100	2 ms	384 KiB

beads

#include<iostream>
#include<vector>
#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> f,g;
// f[i]: max value of subtree rooted at i,
// g[i] = ~ but also include edge from i to parent

static void dfs(int i){
	int sg=0;
	int m1=INT_MIN,m2=INT_MIN; // maximum gain values in score when replace g by f
	// and pair that edge (to node i) where m1 >= m2
	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);
		sg+=g[j];

		int m=f[j]-g[j]+w;
		m2=std::max(m2,m);
		if(m2>m1)std::swap(m1,m2);
	}

	f[i]=sg;
	if(m2!=INT_MIN)
		f[i]=std::max(sg,m1+m2+sg);

	g[i]=f[i];
	if(m1!=INT_MIN)
		g[i]=std::max(g[i],sg+m1+parw[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);
	f.resize(n);
	g.resize(n);
	dfs(0);
	std::cout<<f[0]<<'\n';
}
	

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