Submission #698598

#	Time	Username	Problem	Language	Result	Execution time	Memory
698598		vjudge1	Beads and wires (APIO14_beads)	C++17	100 / 100	310 ms	43208 KiB

beads

/* ...... */

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

#define inl inline
typedef long long ll;
// typedef unsigned long long ull;
// typedef __int128 lll;
// typedef long double llf;
typedef pair <int, int> pint;
#define fst first
#define scd second
#define all(p) begin (p), end (p)
#define empb emplace_back

constexpr int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n, x, y, z, f[N][2], ans;
vector <pint> e[N];
multiset <int> tp[N];

void dfs (int x, int fr) {
	static int tmp;
	for (const auto [y, z] : e[x]) {
		if (y == fr) continue; else dfs (y, x);
		f[x][0] += tmp = max (f[y][0], f[y][1] + z);
		tp[x].emplace (f[y][0] + z - tmp);
	}
	if (tp[x].empty ()) f[x][1] = -INF;
	else f[x][1] = f[x][0] + *rbegin (tp[x]);
}
void dp (int x, int fr) {
	int f_x[2], f_y[2], tmp, numx, numy;
	memcpy (f_x, f[x], 8);
	ans = max (ans, f[x][0]);
	for (const auto [y, z] : e[x]) {
		if (y == fr) continue;
		// * Update new f(x).
		f[x][0] -= tmp = max (f[y][0], f[y][1] + z);
		tp[x].erase (tp[x].find (numx = f[y][0] + z - tmp));
		f[x][1] = tp[x].empty () ? -INF : f[x][0] + *rbegin (tp[x]);
		// * Update new f(y).
		memcpy (f_y, f[y], 8);
		f[y][0] += tmp = max (f[x][0], f[x][1] + z);
		tp[y].emplace (numy = f[x][0] + z - tmp);
		f[y][1] = f[y][0] + *rbegin (tp[y]);
		dp (y, x);
		memcpy (f[x], f_x, 8);
		memcpy (f[y], f_y, 8);
		tp[x].emplace (numx);
		tp[y].erase (tp[y].find (numy));
	}
}

int main () {
	/*  */
	scanf ("%d", &n);
	for (int i = 1; i < n; ++i)
		scanf ("%d%d%d", &x, &y, &z),
		e[x].empb (y, z), e[y].empb (x, z);
	dfs (1, 0); dp (1, 0);
	printf ("%d", ans);

	return 0;
}

Compilation message (stderr)

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

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