oj.uz

답안 #537248

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537248 2022-03-14T19:59:56 Z LucaDantas 구슬과 끈 (APIO14_beads) C++17
0 / 100
 3 ms 4948 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 2e5+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 ans;

void reroot(int u, int p) {
	int sv0 = dp[u][0], sv1 = dp[u][1]; // dou roolback no final

	int sz = (int)(g[u].size());
	vector<array<int,2>> pref(sz), suf(sz);
	
	for(int i = 0; i < sz; i++) {
		auto [v, w] = g[u][i];
		pref[i][1] = max(pref[i][1], dp[v][0] + w - max(dp[v][0], dp[v][1])); // tem que adicionar o peso_pai aqui
		pref[i][0] += max(dp[v][0], dp[v][1]);
	}

	for(int i = sz-1; i >= 0; i--) {
		auto [v, w] = g[u][i];
		suf[i][1] = max(suf[i][1], dp[v][0] + w - max(dp[v][0], dp[v][1])); // tem que adicionar o peso_pai aqui
		suf[i][0] += max(dp[v][0], dp[v][1]);
	}

	ans = max(ans, suf[0][0]);
	
	for(int i = 0; i < sz; i++) {
		if(g[u][i].first == p) continue;
		dp[u][0] = (i ? pref[i-1][0] : 0) + (i < sz-1 ? suf[i+1][0] : 0);
		dp[u][1] = dp[u][0] + max((i ? pref[i-1][1] : 0), (i < sz-1 ? suf[i+1][1] : 0)) + (sz == 1 ? g[u][i].second : 0);
		reroot(g[u][i].first, u);
	}

	dp[u][0] = sv0, dp[u][1] = sv1;
}

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});
	int st;
	for(int i = 1; i <= n; i++)
		if(g[i].size() == 1) st = i; // acho qualquer folha
	dfs(st, 0, 0);
	reroot(st, 0);
	printf("%d\n", ans);
}

Compilation message

beads.cpp: In function 'int main()':
beads.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  int n; scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
beads.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d %d %d", &a, &b, &w), g[a].push_back({b, w}), g[b].push_back({a, w});
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
beads.cpp:60:8: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |  reroot(st, 0);
      |  ~~~~~~^~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -