Submission #135257

#	Time	Username	Problem	Language	Result	Execution time	Memory
135257		pedro_sponchiado	Beads and wires (APIO14_beads)	C++17	0 / 100	15 ms	14456 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;	
	}
	
	int t=filhos[u].size();
	int s=0;
	for(int i=0; i<t; i++) s+=filhos[u][i].second;
	
	//calcula dp1[u]
	if(t>=2){
		dp1[u]=-INF;
		for(int i=0; i<t; i++){
			for(int k=i+1; k<t; k++){
				int aux1=s-filhos[u][i].second-filhos[u][k].second + filhos[u][i].first+filhos[u][k].first;		
				dp1[u]=max(dp1[u], aux1);
			}
		}
	}
	else dp1[u]=s;
	//calcula dp2[u]
	if(p_ar_ant!=-1){
		dp2[u]=-INF;
		for(int i=0; i<t; i++){
			int aux1=s-filhos[u][i].second+filhos[u][i].first;	
			dp2[u]=max(dp2[u], aux1);
		}
		dp2[u]+=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:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:64: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