Submission #169981

#	Time	Username	Problem	Language	Result	Execution time	Memory
169981		ZwariowanyMarcin	Beads and wires (APIO14_beads)	C++14	0 / 100	7 ms	4984 KiB

beads

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;	

const int nax = 2e5 + 111;
const ll inf = 1e18;

int n;
int a, b, c;
vector <pair<int,int>> v[nax];

ll dp[nax][3];

void dfs(int u, int p, int cost) {
	dp[u][0] = 0;
	dp[u][1] = -inf;
	ll sum = 0;
	vector <ll> opt;
	for(auto it : v[u]) 
		if(it.fi != p) {
			dfs(it.fi, u, it.se);
			sum += dp[it.fi][2];
			opt.pb(it.se + dp[it.fi][0] - dp[it.fi][2]);
		}
	sort(opt.begin(), opt.end());
	reverse(opt.begin(), opt.end());
	dp[u][0] = max(dp[u][0], sum);
	if(ss(opt) > 1)
		dp[u][0] = max(dp[u][0], sum + opt[0] + opt[1]);
	if(ss(opt) > 0 && p != 0)
		dp[u][1] = max(dp[u][1], sum + opt[0] + cost);
	dp[u][2] = max(dp[u][0], dp[u][1]);
}
		
		
			
int main() {
	scanf("%d", &n);
	for(int i = 1; i < n; ++i) {
		scanf("%d %d %d", &a, &b, &c);
		v[a].pb(mp(b, c));
		v[b].pb(mp(a, c));
	}
	dfs(1, 0, 0);
	printf("%lld", dp[1][0]);
	
	
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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