Submission #106598

#	Time	Username	Problem	Language	Result	Execution time	Memory
106598		ekrem	Beads and wires (APIO14_beads)	C++98	0 / 100	23 ms	23808 KiB

beads

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define coc g[node][i].st
#define yol g[node][i].nd
#define inf 1000000007
#define N 1000005
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;

int n, dp1[N], dp2[N];
vector < ii > g[N];

void dfs(int node, int par){

	if((int)g[node].size() == 1){
		dp2[node] = -inf;
		return;
	}

	int top = 0, mx = 0, mx2 = 0;
	priority_queue < int > q;
	for(int i = 0; i < g[node].size(); i++){
		if(coc == par)
			continue;
		dfs(coc, node);
		q.push(- max(dp1[coc], yol + dp2[coc]) + dp1[coc] + yol);
		// mx2 = max(mx2, - max(dp1[coc], yol + dp2[coc]) + dp1[coc] + yol);
		// if(mx2 > mx)
		// 	swap(mx, mx2);
		top += max(dp1[coc], yol + dp2[coc]);
	}
	dp2[node] = dp1[node] = top;
	// dp2[node] = max(dp2[node], top + mx);
	// dp1[node] = max(dp1[node], top + mx + mx2);
	for(int i = 0; i < g[node].size(); i++){
		if(coc == par)
			continue;
		dp2[node] = max(dp2[node], top - max(dp1[coc], yol + dp2[coc]) + dp1[coc] + yol);
	}
	if((int)q.size() >= 2){
		int of = q.top();q.pop();
		dp1[node] = max(dp1[node], top + of + q.top());
	}
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d",&n);
	for(int i = 1; i < n; i++){
		int u, v, w;
		scanf("%d %d %d",&u ,&v ,&w);
		g[u].pb(mp(v, w));
		g[v].pb(mp(u, w));
	}
	dfs(1, 0);
	printf("%d\n", dp1[1]);
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++){
                 ~~^~~~~~~~~~~~~~~~
beads.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++){
                 ~~^~~~~~~~~~~~~~~~
beads.cpp:25:15: warning: unused variable 'mx' [-Wunused-variable]
  int top = 0, mx = 0, mx2 = 0;
               ^~
beads.cpp:25:23: warning: unused variable 'mx2' [-Wunused-variable]
  int top = 0, mx = 0, mx2 = 0;
                       ^~~
beads.cpp: In function 'int main()':
beads.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
beads.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&u ,&v ,&w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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