Submission #31628

#	Time	Username	Problem	Language	Result	Execution time	Memory
31628		YoLo	Beads and wires (APIO14_beads)	C++14	0 / 100	6 ms	4992 KiB

beads

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long
#define endl '\n'
#define N 100000
#define pi acos(-1)
#define tora acos(-1)/180
#define tode 180/acos(-1)
#define pque priority_queue
typedef pair < int, int > ii;
typedef vector < int > vi;
typedef vector < vi > vii;
int mod = 1000000007 ;
int d[200009][4], f[200009], a, b, m, n;
vector<ii> v[200009]; 
void dfs(int u, int p)
{
	for(int i = 0; i < v[u].size(); i++)
		if(v[u][i].fi != p)
			dfs(v[u][i].fi, u);
	for(int i = 0; i < v[u].size(); i++)
	{
		int id = v[u][i].fi;
		int l = v[u][i].se;
		if(id == p)
			continue;
		if(d[id][1] > 0)
			d[u][0] += max(d[id][0], d[id][1] + l);
		else
			d[u][0] += d[id][0];
	}
	int cnt = d[u][0];
	for(int i = 0; i < v[u].size(); i++)
	{
		int id = v[u][i].fi;
		int l = v[u][i].se;
		if(id == p)
			continue;
		if(d[id][1] > 0)
			d[u][1] = max(d[u][1], cnt - max(d[id][0], d[id][1] + l) + d[id][0] + l);
		else
			d[u][1] = max(d[u][1], cnt + l);
	}
	int pos;
	if(v[u].size() > 2)
	{
		int cnt2 = - 1e14, cnt3 = -1e14;
		for(int i = 0; i < v[u].size(); i++)
		{
			int id = v[u][i].fi;
			int l = v[u][i].se;
			if(id == p)
				continue;
			if(d[id][1] > 0)
				if(cnt2 <= 0 + d[id][0] + l - max(d[id][0], d[id][1] + l))
					cnt2 = 0 + d[id][0] + l - max(d[id][0], d[id][1] + l), pos = id;
			if(d[id][1] == 0)	
				if(cnt2 <= l )
					cnt2 = l, pos = id;
		}
		for(int i = 0; i < v[u].size(); i++)
		{
			int id = v[u][i].fi;
			int l = v[u][i].se;
			if(id == p || id == pos)
				continue;
			if(d[id][1] > 0)
				if(cnt3 <= 0  + d[id][0] + l- max(d[id][0], d[id][1] + l))
					cnt3 = 0  + d[id][0] + l- max(d[id][0], d[id][1] + l);
			if(d[id][1] == 0)	
				if(cnt3 <= l)
					cnt3 = l;
		}
		d[u][0] = max(d[u][0], cnt + cnt2 + cnt3);
	}
}
signed main()
{
	cin >> n;
	for(int i = 1; i < n; i++)
	{
		cin >> a >> b >> m;
		v[a].pb(mp(b, m));
		v[b].pb(mp(a, m));
	}
	v[1].pb(mp(0, 0));
	dfs(1, 0);
	cout << d[1][0];
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(long long int, long long int)':
beads.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v[u].size(); i++)
                 ~~^~~~~~~~~~~~~
beads.cpp:25:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v[u].size(); i++)
                 ~~^~~~~~~~~~~~~
beads.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v[u].size(); i++)
                 ~~^~~~~~~~~~~~~
beads.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v[u].size(); i++)
                  ~~^~~~~~~~~~~~~
beads.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v[u].size(); i++)
                  ~~^~~~~~~~~~~~~
beads.cpp:69:21: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(id == p || id == pos)
                  ~~~^~~~~~

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