Submission #383381

#	Time	Username	Problem	Language	Result	Execution time	Memory
383381		Saynaa	Beads and wires (APIO14_beads)	C++14	100 / 100	282 ms	25700 KiB

beads

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10;
int n, tmpp[MAXN], dp[MAXN][4];
int mx1[MAXN], mx2[MAXN], DP[MAXN];
vector< pair< int, int> > adj[MAXN];
int ans;

void dfs(int u, int p = -1){
	mx1[u] = mx2[u] = -INT_MAX/2;
	for(int i = 0; i < adj[u].size(); i ++){
		int v = adj[u][i].first, w = adj[u][i].second;
		if( v == p) continue;
		dfs(v, u);
		dp[v][1] += w;
		dp[v][2] = max(dp[v][1], dp[v][0]);
		DP[u] += dp[v][2];
		dp[u][0] += dp[v][2];
		int tmp = dp[v][0] - dp[v][2] + w;
		if( tmp > mx1[u]) mx2[u] = mx1[u], mx1[u] = tmp;
		else if(tmp > mx2[u]) mx2[u] = tmp;
	}
	dp[u][1] = -INT_MAX/2;
	if( mx1[u] > -INT_MAX/2 )
		dp[u][1] = dp[u][0] + mx1[u];
}


void dfs2(int u, int p = -1){
	if( tmpp[u] > mx1[u]) mx2[u] = mx1[u], mx1[u] = tmpp[u];
	else if(tmpp[u] > mx2[u]) mx2[u] = tmpp[u];
	ans = max(ans, DP[u]);
	for(int i= 0; i < adj[u].size(); i ++){
		int v = adj[u][i].first;
		if( v == p) continue;
		int w = adj[u][i].second;
		int idk = DP[u] - dp[v][2];
		int idk2 = dp[v][0] - dp[v][2] + w;
		if( idk2 == mx1[u]) idk2 = mx2[u];
		else idk2 = mx1[u];
		int x = idk;
		if( idk2 != -INT_MAX/2)
			x = max(x, idk + idk2 + w);
		DP[v] += x;
		tmpp[v] = idk + w - x;
		dfs2(v, u);
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1; i < n; i ++){
		int a, b, w;
		cin >> a >> b >> w, a --, b --;
		adj[a].push_back({b, w}), adj[b].push_back({a, w});
	}
	dfs(0);
	tmpp[0] = -INT_MAX/2;
	dfs2(0, 0);
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:13:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for(int i = 0; i < adj[u].size(); i ++){
      |                 ~~^~~~~~~~~~~~~~~
beads.cpp: In function 'void dfs2(int, int)':
beads.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i= 0; i < adj[u].size(); i ++){
      |                ~~^~~~~~~~~~~~~~~

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