Submission #32162

#	Time	Username	Problem	Language	Result	Execution time	Memory
32162		minchurl	Beads and wires (APIO14_beads)	C++11	100 / 100	260 ms	24164 KiB

beads

#include<stdio.h>
#include<math.h>
#include<vector>
#define LL long long
#define MAX_N 200005
#define inf 1000000000000000
#define MAX(x,y) ((x)>(y)?(x):(y))
using namespace std;
struct emp{
	LL y,cost;
};
LL n;
LL master[MAX_N],mid_master[MAX_N],branch[MAX_N],mid_branch[MAX_N];
vector<emp> net[MAX_N];
LL max_cost[4];
emp max_branch[4],max_master[4];
void make_branch(LL x,LL pa,LL cost){
	LL i,sz;
	LL maxx=0,y,z=0;
	sz=net[x].size();
	for(i=0;i<sz;i++){
		if(net[x][i].y==pa)	continue;
		maxx+=mid_branch[net[x][i].y];
	}
	maxx=MAX(maxx,branch[x]);
	for(i=0;i<sz;i++){
		if(net[x][i].y==pa)	continue;
		y=cost+net[x][i].cost+branch[x]-mid_branch[net[x][i].y]+branch[net[x][i].y];
		//printf("%lld %lld %lld %lld\n",pa,x,net[x][i].y,y);
		maxx=MAX(maxx,y);
	}
	mid_branch[x]=MAX(mid_branch[x],maxx);
	branch[pa]+=mid_branch[x];
}
void make_master(LL x,LL pa,LL cost){
	LL i,y,sz;
	sz=net[x].size();
	mid_master[x]=MAX(mid_master[x],master[x]);
	for(i=0;i<sz;i++){
		if(net[x][i].y==pa)	continue;
		y=master[net[x][i].y]+cost+net[x][i].cost+branch[x]-mid_branch[net[x][i].y];
		mid_master[x]=MAX(mid_master[x],y);
	}
	for(i=0;i<sz;i++){
		if(net[x][i].y==pa)	continue;
		y=branch[x]-mid_branch[net[x][i].y]+master[net[x][i].y];
		master[x]=MAX(master[x],y);
		y=mid_master[net[x][i].y]+branch[x]-mid_branch[net[x][i].y];
		master[x]=MAX(master[x],y);
	}
}
void merge(LL x,LL pa,LL cost){
	LL i,sz;
	LL y,z;
	
	max_cost[0]=max_cost[1]=-inf;
	sz=net[x].size();
	if(pa && sz<3)	return;
	if(!pa && sz<2)	return;
	for(i=0;i<sz;i++){
		if(net[x][i].y==pa)	continue;
		y=-mid_branch[net[x][i].y]+net[x][i].cost+branch[net[x][i].y];
		if(max_cost[0]<y){
			max_cost[1]=max_cost[0];
			max_cost[0]=y;
		}else if(max_cost[1]<y){
			max_cost[1]=y;
		}
	}
	master[x]=MAX(master[x],branch[x]+max_cost[0]+max_cost[1]);
	max_branch[0].cost=max_branch[1].cost=-inf;
	max_branch[0].y=max_branch[1].y=-1;
	max_master[0].cost=max_master[1].cost=-inf;
	max_master[0].y=max_master[1].y=-1;
	for(i=0;i<sz;i++){
		if(net[x][i].y==pa)	continue;
		y=-mid_branch[net[x][i].y]+branch[net[x][i].y]+net[x][i].cost;
		if(y>max_branch[0].cost){
			max_branch[1]=max_branch[0];
			max_branch[0].cost=y;
			max_branch[0].y=net[x][i].y;
		}else if(y>max_branch[1].cost){
			max_branch[1].cost=y;
			max_branch[1].y=net[x][i].y;
		}
	}
	for(i=0;i<sz;i++){
		if(net[x][i].y==pa)	continue;
		y=-mid_branch[net[x][i].y]+master[net[x][i].y]+net[x][i].cost;
		if(y>max_master[0].cost){
			max_master[1]=max_master[0];
			max_master[0].cost=y;
			max_master[0].y=net[x][i].y;
		}else if(y>max_master[1].cost){
			max_master[1].cost=y;
			max_master[1].y=net[x][i].y;
		}
	}
	//printf("%lld : %lld %lld : %lld %lld\n",x,max_branch[0].y,max_branch[1].y,max_master[0].y,max_branch[1].y);
	if(max_master[0].y-max_branch[0].y){
		master[x]=MAX(master[x],max_master[0].cost+max_branch[0].cost+branch[x]);
	}else{
		master[x]=MAX(master[x],MAX(max_master[0].cost+max_branch[1].cost,max_master[1].cost+max_branch[0].cost)+branch[x]);
	}
}
void make_ans(LL x,LL pa,LL cost){
	LL i,sz,y;
	sz=net[x].size();
	for(i=0;i<sz;i++){
		if(net[x][i].y==pa)	continue;
		make_ans(net[x][i].y,x,net[x][i].cost);
	}
	make_branch(x,pa,cost);
	merge(x,pa,cost);
	make_master(x,pa,cost);
	master[pa]=MAX(master[pa],master[x]);
	//printf("%lld : %lld %lld %lld\n",x,master[x],branch[x],mid_branch[x]);
}
int main(){
	LL i,x,y,cost;
	emp node;
	scanf("%lld",&n);
	for(i=1;i<n;i++){
		scanf("%lld %lld %lld",&x,&y,&cost);
		node.y=y;
		node.cost=cost;
		net[x].push_back(node);
		node.y=x;
		net[y].push_back(node);
	}
	make_ans(1,0,0);
	printf("%lld\n",MAX(master[1],branch[1]));
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void make_branch(long long int, long long int, long long int)':
beads.cpp:19:14: warning: unused variable 'z' [-Wunused-variable]
  LL maxx=0,y,z=0;
              ^
beads.cpp: In function 'void merge(long long int, long long int, long long int)':
beads.cpp:54:7: warning: unused variable 'z' [-Wunused-variable]
  LL y,z;
       ^
beads.cpp: In function 'void make_ans(long long int, long long int, long long int)':
beads.cpp:107:10: warning: unused variable 'y' [-Wunused-variable]
  LL i,sz,y;
          ^
beads.cpp: In function 'int main()':
beads.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
beads.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&x,&y,&cost);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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