Submission #135249

#	Time	Username	Problem	Language	Result	Execution time	Memory
135249		pedro_sponchiado	Beads and wires (APIO14_beads)	C++17	0 / 100	15 ms	14584 KiB

beads

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000;
const int INF=1000000000;
int n;
vector<int> adj[maxn], peso[maxn];

int dp1[maxn], dp2[maxn];
int marc[maxn];

vector<pair<int, int> > filhos[maxn]; 
vector<int> aux;

void dfs(int u, int p_ar_ant){
	marc[u]=1;
	
	int folha=1;
	for(int i=0; i<adj[u].size(); i++){
		int v=adj[u][i];
		
		if(marc[v]==0){
			folha=0;
			dfs(v, peso[u][i]);
			
			filhos[u].push_back(make_pair(dp1[v]+peso[u][i], max(dp1[v], dp2[v])));
		}
	}
	if(folha){
		dp1[u]=0;
		dp2[u]=-INF;
		return;	
	}
	
//	printf("%d:\n", u);
	
	int t=filhos[u].size();
	
	aux.clear();
	int s=0;
	for(int i=0; i<t; i++){
//  	printf("%d %d\n", filhos[u][i].first, filhos[u][i].second);
		
		s+=filhos[u][i].second;
		aux.push_back(filhos[u][i].first-filhos[u][i].second);
	}
	sort(aux.begin(), aux.end());
	
	//calcula dp1[u]
	if(t>=2 && (aux[t-1]+aux[t-2]>0) ) dp1[u]=s+aux[t-1]+aux[t-2];
	else dp1[u]=s;
	
	//calcula dp2[u]
	if(p_ar_ant!=-1) dp2[u]=s+aux[t-1]+p_ar_ant;  
	
	
	return;
}

int main(){
	scanf("%d", &n);
	for(int a, b, p, i=1; i<=n-1; i++){
		scanf("%d %d %d", &a, &b, &p);
		adj[a].push_back(b);
		adj[b].push_back(a);
		peso[a].push_back(p);
		peso[b].push_back(p);	
	}
	
	dfs(1, -1);
	
/*	printf("\n\n");
	for(int i=1; i<=n; i++){
		printf("%d: %d %d\n", i, dp1[i], dp2[i]);
	}	
*/		
	printf("%d\n", dp1[1]);
		
	return 0;
}	

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:18:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<adj[u].size(); i++){
               ~^~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a, &b, &p);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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