Submission #135093

#	Time	Username	Problem	Language	Result	Execution time	Memory
135093		wmrmr	Beads and wires (APIO14_beads)	C++17	0 / 100	14 ms	14456 KiB

beads

#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5+10, INF = 2e9+2;

vector<int> g[MAX],id[MAX],w[MAX];
int dp[MAX][2];
int ans, r;

void DFS(int v, int e)
{
	int grau = g[v].size();
	if(grau == 1) 
	{
		if(e!=0) return;
		int prox = g[v][0], edge = id[v][0], peso = w[v][0];
		DFS(prox,edge);
		dp[v][0] = dp[prox][0];
	}
	int sum = 0;
	int big = -INF, bigger = -INF;
	for(int i=0;i<grau;i++)
	{
		int prox = g[v][i], edge = id[v][i], peso = w[v][i];
		int dif;
		if(edge == e) dif = peso;
		else
		{
			DFS(prox,edge);
			sum += dp[prox][0];
			dif = dp[prox][1] + peso - dp[prox][0];	
		}
		if(dif > bigger)
		{
			big = bigger;
			bigger = dif;
		}
		else if( dif > big ) big = dif;
	}
	dp[v][0] = max(sum,sum+big+bigger);
	big = -INF; bigger = -INF;
	for(int i=0;i<grau;i++)
	{
		int prox = g[v][i], edge = id[v][i], peso = w[v][i];
		int dif;
		if(edge == e) continue;
		dif = dp[prox][1] + peso - dp[prox][0];	
		if(dif > bigger)
		{
			big = bigger;
			bigger = dif;
		}
		else if( dif > big ) big = dif;
	}
	dp[v][1] = max(sum,sum+big+bigger);
	return;
}

int main()
{
	int n; scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int a,b,c; scanf("%d %d %d",&a,&b,&c);
		g[a].push_back(b); g[b].push_back(a);
		id[a].push_back(i); id[b].push_back(i);
		w[a].push_back(c); w[b].push_back(c);
	}
	for(r=1;r<=n;r++)
	{
		if(g[r].size() == 1){ DFS(r,0); break; };
	}
	printf("%d\n",r);
	for(int i=1;i<=n;i++)
	{
		printf("%d %d | ",dp[i][0],dp[i][1]);
	}
}

Compilation message (stderr)

beads.cpp: In function 'void DFS(int, int)':
beads.cpp:15:40: warning: unused variable 'peso' [-Wunused-variable]
   int prox = g[v][0], edge = id[v][0], peso = w[v][0];
                                        ^~~~
beads.cpp: In function 'int main()':
beads.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d",&n);
         ~~~~~^~~~~~~~~
beads.cpp:63:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a,b,c; scanf("%d %d %d",&a,&b,&c);
              ~~~~~^~~~~~~~~~~~~~~~~~~~~

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