Submission #30646

#	Time	Username	Problem	Language	Result	Execution time	Memory
30646		ulna	Beads and wires (APIO14_beads)	C++11	100 / 100	429 ms	32664 KiB

beads

#include <bits/stdc++.h>
using namespace std;

// why am I so weak

int n;

struct edge {int to; long long cost;};

vector<edge> g[200055];

inline void add_edge(int from, int to, int cost) {
	g[from].push_back((edge){to, cost});
}

long long dp[200055][2];

void dfs(int v, int par = -1) {
	dp[v][0] = 0;
	dp[v][1] = -(long long)1e13;
	
	// one dp[e.to][0] + e.cost
	
	long long sum = 0ll;

	for (auto e : g[v]) if (e.to != par) {
		dfs(e.to, v);

		dp[v][0] += max(dp[e.to][0], dp[e.to][1] + e.cost);
		sum += max(dp[e.to][0], dp[e.to][1] + e.cost);
	}

	for (auto e : g[v]) if (e.to != par) {
		dp[v][1] = max(dp[v][1], sum - max(dp[e.to][0], dp[e.to][1] + e.cost) + dp[e.to][0] + e.cost);
	}
}

struct dat {long long dat[2];};

long long rdfs(int v, int par, dat ac, long long cost) {
	long long res = dp[v][0] + max(ac.dat[0], ac.dat[1] + cost);

	dat cool;
	cool.dat[0] = 0;
	cool.dat[1] = -(long long)1e13;

	multiset<long long> s;
	long long sum = 0;

	for (auto e : g[v]) if (e.to != par) {
		cool.dat[0] += max(dp[e.to][0], dp[e.to][1] + e.cost);
		sum += max(dp[e.to][0], dp[e.to][1] + e.cost);
		
		s.insert(-max(dp[e.to][0], dp[e.to][1] + e.cost) + dp[e.to][0] + e.cost);
	}

	cool.dat[0] += max(ac.dat[0], ac.dat[1] + cost);
	sum += max(ac.dat[0], ac.dat[1] + cost);

	s.insert(-max(ac.dat[0], ac.dat[1] + cost) + ac.dat[0] + cost);

	for (auto e : g[v]) if (e.to != par) {
		s.erase(s.find(-max(dp[e.to][0], dp[e.to][1] + e.cost) + dp[e.to][0] + e.cost));

		cool.dat[0] -= max(dp[e.to][0], dp[e.to][1] + e.cost);
		cool.dat[1] = sum + *s.rbegin() - max(dp[e.to][0], dp[e.to][1] + e.cost);

		res = max(res, rdfs(e.to, v, cool, e.cost));
		
		cool.dat[0] += max(dp[e.to][0], dp[e.to][1] + e.cost);

		s.insert(-max(dp[e.to][0], dp[e.to][1] + e.cost) + dp[e.to][0] + e.cost);
	}

	return res;
}
int main() {
	scanf("%d", &n);

	for (int i = 1; i < n; i++) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		x--, y--;

		add_edge(x, y, z);
		add_edge(y, x, z);
	}

	dfs(0);

	dat a;
	a.dat[0] = 0;
	a.dat[1] = -(long long)1e13;
	
	printf("%lld\n", rdfs(0, -1, a, -(long long)1e13));

	return 0;
}

Compilation message (stderr)

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

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