Submission #31927

#	Time	Username	Problem	Language	Result	Execution time	Memory
31927		minchurl	Beads and wires (APIO14_beads)	C++11	0 / 100	5 ms	4992 KiB

beads

#include<stdio.h>
#include<math.h>
#include<vector>
#define LL long long
#define MAX_N 200005
#define MAX(x,y) ((x)>(y)?(x):(y))
#define inf 100000000000000LL
using namespace std;
struct emp{
	LL y,cost;
	bool operator < (emp d) const{
		return cost>d.cost;
	}
};
LL n;
LL t[5][MAX_N];
vector<emp> net[MAX_N];
void make_ans(LL x,LL pa,LL cost){
	LL i,sz,y,max_cost[4]={-inf,-inf},sum,z=0;
	sz=net[x].size();
	for(i=0;i<sz;i++){
		y=net[x][i].y;
		if(y==pa)	continue;
		z++;
		make_ans(y,x,net[x][i].cost);
		t[0][x]+=MAX(t[0][y],MAX(t[1][y],t[2][y]));
	}
	if(z<1)	return;
	if(pa!=0){
		for(i=0;i<sz;i++){
			y=net[x][i].y;
			if(y==pa)	continue;
			if(t[1][y]>t[0][y] && t[1][y]>t[2][y]){
				sum=t[0][x]-t[1][y]+MAX(t[0][y],t[2][y])+net[x][i].cost+cost;
			}else{
				sum=t[0][x]+net[x][i].cost+cost;
			}
			t[1][x]=MAX(t[1][x],sum);
		}
	}
	if(z<2)	return;
	for(i=0;i<sz;i++){
		y=net[x][i].y;
		if(y==pa)	continue;
		if(t[1][y]>t[0][y] && t[1][y]>t[2][y]){
			sum=MAX(t[0][y],t[2][y])-t[1][y]+net[x][i].cost;
		}else{
			sum=net[x][i].cost;
		}
		if(sum>max_cost[0]){
			max_cost[1]=max_cost[0];
			max_cost[0]=sum;
		}else if(sum>max_cost[1]){
			max_cost[1]=sum;
		}
	}
	t[2][x]=max_cost[0]+max_cost[1]+t[0][x];
	return;
}
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(t[0][1],MAX(t[1][1],t[2][1])));
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
beads.cpp:65: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: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43