Submission #125121

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
125121	2019-07-04T16:22:30 Z	TadijaSebez	Beads and wires (APIO14_beads)	C++11	57 / 100	41 ms	6140 KB

beads

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
const int inf=1e9+7;
vector<pair<int,int>> E[N];
int dp[N][2],up[N][2];
void DFS(int u, int p, int w)
{
	dp[u][0]=0;
	int mx=-inf;
	for(auto e:E[u]) if(e.first!=p)
	{
		int v=e.first;
		DFS(v,u,e.second);
		dp[u][0]+=max(dp[v][0],dp[v][1]);
		mx=max(mx,dp[v][0]+w+e.second-max(dp[v][0],dp[v][1]));
	}
	dp[u][1]=dp[u][0]+mx;
}
int ans;
void Solve(int u, int p, int w)
{
	ans=max(ans,max(up[u][0],up[u][1])+dp[u][0]);
	int fir=-inf,sec=-inf,cnt=0;
	for(auto e:E[u]) if(e.first!=p)
	{
		int v=e.first;
		int tmp=dp[v][0]-max(dp[v][0],dp[v][1])+e.second;
		if(fir<tmp) sec=fir,fir=tmp;
		else if(sec<tmp) sec=tmp;
		cnt++;
	}
	for(auto e:E[u]) if(e.first!=p)
	{
		int v=e.first;
		int tmp=dp[v][0]-max(dp[v][0],dp[v][1])+e.second;
		int sum=dp[u][0]-max(dp[v][0],dp[v][1]);
		if(u!=1) up[v][1]=up[u][0]+w+e.second+sum;
		if(cnt>1)
		{
			int add=fir;
			if(fir==tmp) add=sec;
			up[v][1]=max(up[v][1],max(up[u][1],up[u][0])+e.second+add+sum);
		}
		up[v][0]=max(up[u][0],up[u][1])+sum;
		Solve(v,u,e.second);
	}
}
int main()
{
	int n,u,v,w;
	scanf("%i",&n);
	for(int i=1;i<n;i++) scanf("%i %i %i",&u,&v,&w),E[u].pb({v,w}),E[v].pb({u,w});
	DFS(1,0,0);
	Solve(1,0,0);
    printf("%i\n",ans);
	return 0;
}

Compilation message

beads.cpp: In function 'int main()':
beads.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
beads.cpp:54:64: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<n;i++) scanf("%i %i %i",&u,&v,&w),E[u].pb({v,w}),E[v].pb({u,w});
                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2680 KB	Output is correct
2	Correct	5 ms	2680 KB	Output is correct
3	Correct	5 ms	2684 KB	Output is correct
4	Correct	5 ms	2680 KB	Output is correct
5	Correct	4 ms	2680 KB	Output is correct
6	Correct	4 ms	2680 KB	Output is correct
7	Correct	4 ms	2684 KB	Output is correct
8	Correct	4 ms	2680 KB	Output is correct
9	Correct	4 ms	2680 KB	Output is correct
10	Correct	4 ms	2684 KB	Output is correct
11	Correct	4 ms	2680 KB	Output is correct
12	Correct	4 ms	2680 KB	Output is correct
13	Correct	4 ms	2680 KB	Output is correct
14	Correct	4 ms	2808 KB	Output is correct
15	Correct	4 ms	2680 KB	Output is correct
16	Correct	4 ms	2680 KB	Output is correct
17	Correct	4 ms	2684 KB	Output is correct
18	Correct	4 ms	2680 KB	Output is correct
19	Correct	4 ms	2680 KB	Output is correct
20	Correct	4 ms	2708 KB	Output is correct
21	Correct	4 ms	2680 KB	Output is correct
22	Correct	4 ms	2680 KB	Output is correct
23	Correct	7 ms	2936 KB	Output is correct
24	Correct	8 ms	2936 KB	Output is correct
25	Correct	7 ms	2936 KB	Output is correct
26	Correct	12 ms	3372 KB	Output is correct
27	Correct	11 ms	3320 KB	Output is correct
28	Correct	9 ms	3448 KB	Output is correct
29	Correct	10 ms	3448 KB	Output is correct
30	Correct	10 ms	3320 KB	Output is correct
31	Correct	12 ms	3704 KB	Output is correct

Subtask #4
0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2680 KB	Output is correct
2	Correct	5 ms	2680 KB	Output is correct
3	Correct	5 ms	2684 KB	Output is correct
4	Correct	5 ms	2680 KB	Output is correct
5	Correct	4 ms	2680 KB	Output is correct
6	Correct	4 ms	2680 KB	Output is correct
7	Correct	4 ms	2684 KB	Output is correct
8	Correct	4 ms	2680 KB	Output is correct
9	Correct	4 ms	2680 KB	Output is correct
10	Correct	4 ms	2684 KB	Output is correct
11	Correct	4 ms	2680 KB	Output is correct
12	Correct	4 ms	2680 KB	Output is correct
13	Correct	4 ms	2680 KB	Output is correct
14	Correct	4 ms	2808 KB	Output is correct
15	Correct	4 ms	2680 KB	Output is correct
16	Correct	4 ms	2680 KB	Output is correct
17	Correct	4 ms	2684 KB	Output is correct
18	Correct	4 ms	2680 KB	Output is correct
19	Correct	4 ms	2680 KB	Output is correct
20	Correct	4 ms	2708 KB	Output is correct
21	Correct	4 ms	2680 KB	Output is correct
22	Correct	4 ms	2680 KB	Output is correct
23	Correct	7 ms	2936 KB	Output is correct
24	Correct	8 ms	2936 KB	Output is correct
25	Correct	7 ms	2936 KB	Output is correct
26	Correct	12 ms	3372 KB	Output is correct
27	Correct	11 ms	3320 KB	Output is correct
28	Correct	9 ms	3448 KB	Output is correct
29	Correct	10 ms	3448 KB	Output is correct
30	Correct	10 ms	3320 KB	Output is correct
31	Correct	12 ms	3704 KB	Output is correct
32	Correct	41 ms	6140 KB	Output is correct
33	Correct	41 ms	6108 KB	Output is correct
34	Correct	39 ms	6008 KB	Output is correct
35	Runtime error	7 ms	5116 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
36	Halted	0 ms	0 KB	-

Submission #125121

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 15.0 / 15.0

Subtask #3 29.0 / 29.0

Subtask #4 0 / 43.0

Subtask #1
13.0 / 13.0

Subtask #2
15.0 / 15.0

Subtask #3
29.0 / 29.0

Subtask #4
0 / 43.0