Submission #7467

#	Time	Username	Problem	Language	Result	Execution time	Memory
7467		gs13068	Beads and wires (APIO14_beads)	C++98	100 / 100	244 ms	25424 KiB

beads

#include<cstdio>
#include<vector>
#include<algorithm>

std::vector<std::pair<int,int> > tr[200001];
int v[200001];
int d1[200001]; // none
int d2[200001]; // I
int d3[200001]; // V
int d4[200001]; // Y

void dfs(int x,int y)
{
	int m2,m31,m32,m32_1,m32_2,m4;
    int i;
	v[x]=1;
	m2=m31=m32=m32_1=m32_2=m4=-1e9;
    for(i=0;i<tr[x].size();i++)if(!v[tr[x][i].first])
	{
        dfs(tr[x][i].first,tr[x][i].second);

        d1[x]+=std::max(d1[tr[x][i].first],d2[tr[x][i].first]);

        d2[x]+=std::max(d1[tr[x][i].first],d2[tr[x][i].first]);
        m2=std::max(m2,y+tr[x][i].second+d1[tr[x][i].first]-std::max(d1[tr[x][i].first],d2[tr[x][i].first]));

        d3[x]+=std::max(d1[tr[x][i].first],d2[tr[x][i].first]);
		m31=std::max(m31,std::max(d3[tr[x][i].first],d4[tr[x][i].first])-std::max(d1[tr[x][i].first],d2[tr[x][i].first]));
        m32=std::max(m32,m32_1+tr[x][i].second+d1[tr[x][i].first]-std::max(d1[tr[x][i].first],d2[tr[x][i].first]));
        m32=std::max(m32,m32_2+tr[x][i].second+d3[tr[x][i].first]-std::max(d1[tr[x][i].first],d2[tr[x][i].first]));
		m32_1=std::max(m32_1,tr[x][i].second+d3[tr[x][i].first]-std::max(d1[tr[x][i].first],d2[tr[x][i].first]));
        m32_2=std::max(m32_2,tr[x][i].second+d1[tr[x][i].first]-std::max(d1[tr[x][i].first],d2[tr[x][i].first]));

        d4[x]+=std::max(d1[tr[x][i].first],d2[tr[x][i].first]);
        m4=std::max(m4,y+tr[x][i].second+d3[tr[x][i].first]-std::max(d1[tr[x][i].first],d2[tr[x][i].first]));
	}
	d2[x]+=std::max(0,m2);
	d3[x]+=std::max(0,std::max(m31,m32));
	d4[x]+=std::max(0,m4);
}

int main()
{
	int a,b,c;
	int i,n;
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		tr[a].push_back(std::make_pair(b,c));
		tr[b].push_back(std::make_pair(a,c));
	}
	dfs(1,-1e9);
	printf("%d",std::max(std::max(d1[1],d2[1]),std::max(d3[1],d4[1])));
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:18:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<tr[x].size();i++)if(!v[tr[x][i].first])
             ~^~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
beads.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a,&b,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~

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