oj.uz

Submission #338105

# Submission time Handle Problem Language Result Execution time Memory
338105 2020-12-22T13:53:57 Z ogibogi2004 Beads and wires (APIO14_beads) C++14
28 / 100
 1000 ms 5484 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+6;
const ll INF=2e15;
ll dp[MAXN][2];
ll par[MAXN];
vector<pair<ll,ll> >g[MAXN];
void dfs(ll u,ll p)
{
	par[u]=p;
	vector<pair<pair<ll,ll>,ll> >ch;
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		dfs(v.first,u);
		ch.push_back({{dp[v.first][0],dp[v.first][1]},v.second});
	}
	dp[u][1]=-INF;
	for(ll i=0;i<ch.size();i++)
	{
		dp[u][0]+=max(ch[i].first.first,ch[i].first.second+ch[i].second);
	}
	for(ll i=0;i<ch.size();i++)
	{
		dp[u][1]=max(dp[u][1],dp[u][0]-max(ch[i].first.first,ch[i].first.second+ch[i].second)+ch[i].first.first+ch[i].second);
	}
}
int main()
{
	ll n;
	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});
	}
	ll ans=0;
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=n;j++)
		{
			dp[j][0]=0;
			dp[j][1]=-INF;
		}
		dfs(i,0);
		//cout<<i<<" "<<dp[i][0]<<endl;
		ans=max(ans,dp[i][0]);
	}
	cout<<ans<<endl;
return 0;
}
/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34

*/

Compilation message

beads.cpp: In function 'void dfs(long long int, long long int)':
beads.cpp:20:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(ll i=0;i<ch.size();i++)
      |             ~^~~~~~~~~~
beads.cpp:24:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(ll i=0;i<ch.size();i++)
      |             ~^~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 4972 KB Output is correct
5 Correct 4 ms 4972 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4972 KB Output is correct
8 Correct 4 ms 4972 KB Output is correct
9 Correct 4 ms 4972 KB Output is correct
10 Correct 4 ms 4972 KB Output is correct
11 Correct 4 ms 4972 KB Output is correct
12 Correct 4 ms 4972 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 4972 KB Output is correct
5 Correct 4 ms 4972 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4972 KB Output is correct
8 Correct 4 ms 4972 KB Output is correct
9 Correct 4 ms 4972 KB Output is correct
10 Correct 4 ms 4972 KB Output is correct
11 Correct 4 ms 4972 KB Output is correct
12 Correct 4 ms 4972 KB Output is correct
13 Correct 4 ms 5100 KB Output is correct
14 Correct 4 ms 5100 KB Output is correct
15 Correct 4 ms 5100 KB Output is correct
16 Correct 6 ms 5100 KB Output is correct
17 Correct 6 ms 5100 KB Output is correct
18 Correct 6 ms 5100 KB Output is correct
19 Correct 5 ms 5100 KB Output is correct
20 Correct 5 ms 5100 KB Output is correct
21 Correct 5 ms 5100 KB Output is correct
22 Correct 6 ms 5100 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 4972 KB Output is correct
5 Correct 4 ms 4972 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4972 KB Output is correct
8 Correct 4 ms 4972 KB Output is correct
9 Correct 4 ms 4972 KB Output is correct
10 Correct 4 ms 4972 KB Output is correct
11 Correct 4 ms 4972 KB Output is correct
12 Correct 4 ms 4972 KB Output is correct
13 Correct 4 ms 5100 KB Output is correct
14 Correct 4 ms 5100 KB Output is correct
15 Correct 4 ms 5100 KB Output is correct
16 Correct 6 ms 5100 KB Output is correct
17 Correct 6 ms 5100 KB Output is correct
18 Correct 6 ms 5100 KB Output is correct
19 Correct 5 ms 5100 KB Output is correct
20 Correct 5 ms 5100 KB Output is correct
21 Correct 5 ms 5100 KB Output is correct
22 Correct 6 ms 5100 KB Output is correct
23 Execution timed out 1096 ms 5484 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 4972 KB Output is correct
5 Correct 4 ms 4972 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4972 KB Output is correct
8 Correct 4 ms 4972 KB Output is correct
9 Correct 4 ms 4972 KB Output is correct
10 Correct 4 ms 4972 KB Output is correct
11 Correct 4 ms 4972 KB Output is correct
12 Correct 4 ms 4972 KB Output is correct
13 Correct 4 ms 5100 KB Output is correct
14 Correct 4 ms 5100 KB Output is correct
15 Correct 4 ms 5100 KB Output is correct
16 Correct 6 ms 5100 KB Output is correct
17 Correct 6 ms 5100 KB Output is correct
18 Correct 6 ms 5100 KB Output is correct
19 Correct 5 ms 5100 KB Output is correct
20 Correct 5 ms 5100 KB Output is correct
21 Correct 5 ms 5100 KB Output is correct
22 Correct 6 ms 5100 KB Output is correct
23 Execution timed out 1096 ms 5484 KB Time limit exceeded
24 Halted 0 ms 0 KB -