oj.uz

Submission #337400

# Submission time Handle Problem Language Result Execution time Memory
337400 2020-12-20T14:35:09 Z ogibogi2004 Beads and wires (APIO14_beads) C++14
0 / 100
 2 ms 2668 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll MAXN=1e5+6;
const ll INF=2e18;
ll dp[MAXN][2];
ll dp1[MAXN][3];
vector<pair<ll,ll> >g[MAXN];
ll n;
struct node
{
	ll idx;
	ll pare;
	ll v1,v2,v3;
};
void dfs(ll u,ll par)
{
	vector<node>children;
	for(auto v:g[u])
	{
		if(v.first==par)continue;
		dfs(v.first,u);
		children.push_back({v.first,v.second,dp[v.first][0],dp[v.first][1]+v.second,dp[v.first][0]+v.second});
	}
	if(children.size()==0)
	{
		dp[u][0]=0;
		dp[u][1]=-INF;
		return;
	}
	dp1[0][0]=max(children[0].v1,children[0].v2);
	dp1[0][1]=children[0].v3;
	dp1[0][2]=-INF;
	for(ll i=1;i<children.size();++i)
	{
		dp1[i][0]=0;
		dp1[i][1]=-INF;
		dp1[i][2]=-INF;
		dp1[i][0]=max(dp1[i][0],dp1[i-1][0]+children[i].v1);
		dp1[i][0]=max(dp1[i][0],dp1[i-1][0]+children[i].v2);
		dp1[i][1]=max(dp1[i][1],dp1[i-1][1]+children[i].v1);
		dp1[i][1]=max(dp1[i][1],dp1[i-1][1]+children[i].v2);
		dp1[i][2]=max(dp1[i][2],dp1[i-1][2]+children[i].v1);
		dp1[i][2]=max(dp1[i][2],dp1[i-1][2]+children[i].v2);
		dp1[i][1]=max(dp1[i][1],dp1[i-1][0]+children[i].v3);
		dp1[i][2]=max(dp1[i][2],dp1[i-1][1]+children[i].v3);
	}
	dp[u][0]=max(dp1[children.size()-1][0],dp1[children.size()-1][2]);
	dp[u][1]=dp1[children.size()-1][1];
}
int main()
{
	cin>>n;
	for(ll i=1;i<n;i++)
	{
		ll x,y,z;
		cin>>x>>y>>z;
		g[x].push_back({y,z});
		g[y].push_back({x,z});
	}
	dfs(1,0);
	cout<<dp[1][0]<<endl;
return 0;
}

Compilation message

beads.cpp:5:14: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
    5 | const ll INF=2e18;
      |              ^~~~
beads.cpp: In function 'void dfs(int, int)':
beads.cpp:34:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(ll i=1;i<children.size();++i)
      |             ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Incorrect 2 ms 2668 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Incorrect 2 ms 2668 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Incorrect 2 ms 2668 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Incorrect 2 ms 2668 KB Output isn't correct
7 Halted 0 ms 0 KB -