Submission #537233

#	Time	Username	Problem	Language	Result	Execution time	Memory
537233		LucaDantas	Beads and wires (APIO14_beads)	C++17	28 / 100	1075 ms	1108 KiB

beads

// provavelmente vai dar errado, e com certeza da tle nas maiores
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 1e4+10; // subtask mudar

vector<pair<int,int>> g[maxn];

int dp[maxn][2]; // posso retornar com o pai livre ou sem o pai livre

void dfs(int u, int p, int peso_pai) {
	for(auto [v, w] : g[u]) if(v != p) {
		dfs(v, u, w);
		dp[u][1] = max(dp[u][1], dp[v][0] + w + peso_pai - max(dp[v][0], dp[v][1]));
		dp[u][0] += max(dp[v][0], dp[v][1]);
	}
	dp[u][1] += dp[u][0];
	// printf("%d -> %d %d\n", u, dp[u][0], dp[u][1]);
}

int main() {
	int n; scanf("%d", &n);
	for(int i = 1, a, b, w; i < n; i++)
		scanf("%d %d %d", &a, &b, &w), g[a].push_back({b, w}), g[b].push_back({a, w});
	// comeco de uma folha pq é mais facil
	int ans = 0;
	for(int i = 1; i <= n; i++)
		if(g[i].size() == 1)
			dfs(i, 0, 0), ans = max(ans, dp[i][0]), memset(dp, 0, sizeof dp);
	printf("%d\n", ans);
	/* int st = -1;
	for(int i = 1; i < n; i++)
		if(g[i].size() == 1) st = i;
	dfs(st, 0, 0);
	printf("%d\n", dp[st][0]); */
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  int n; scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
beads.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   scanf("%d %d %d", &a, &b, &w), g[a].push_back({b, w}), g[b].push_back({a, w});
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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