Submission #159130

#	Time	Username	Problem	Language	Result	Execution time	Memory
159130		sealnot123	Beads and wires (APIO14_beads)	C++14	100 / 100	205 ms	24824 KiB

beads

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
const int N=200005;

LL dp[N][2], p[N];
vector<PII> g[N];

void DP(int u, int v){
	int ch = 0;
	dp[u][1] = -1e18;
	LL b = -1e18;
	for(PII e: g[u]){
		if(e.x == v) continue;
		DP(e.x, u);
		LL a = max(dp[e.x][0], dp[e.x][1]+e.y);
		dp[u][1] = max(dp[u][1]+a, dp[u][0]+dp[e.x][0]+e.y);
		dp[u][0] += a;	

		p[e.x] = b;
		b = max(b, -a+dp[e.x][0]+e.y);
	}
	b = -1e18;
	for(int i = g[u].size()-1; i >= 0; i--){
		PII e = g[u][i];
		if(e.x == v) continue;
		p[e.x] = max(p[e.x], b);
		LL a = max(dp[e.x][0], dp[e.x][1]+e.y);
		b = max(b, -a+dp[e.x][0]+e.y);
	}
}

LL dfs(int u, int v, LL a, LL b, LL w){
	LL X = max(0ll,max(a,b+w));
	LL ans = dp[u][0]+X;
	//printf("%lld %lld %lld %lld %d\n", ans, a, b, w, u); 
	for(PII e : g[u]){
		if(e.x == v) continue;
		LL c = max(dp[e.x][0], dp[e.x][1]+e.y);
		LL A = dp[u][0]-c+X;
		LL B = dp[u][0]-c+max(p[e.x]+X, a+w);
		ans = max(ans, dfs(e.x, u, A, B, e.y));
	}
	return ans;
}

int main(){
	int i,j,k,l,a,b,c,d;
	int n;
	scanf("%d",&n);
	for(i=1;i<n;i++){
		scanf("%d%d%d",&a,&b,&c);
		g[a].push_back({b,c});
		g[b].push_back({a,c});
	}
	DP(1,1);
	//for(i=1;i<=n;i++) printf("%d %lld %lld %lld\n",i,dp[i][0],dp[i][1],p[i]);
	printf("%lld",dfs(1,1,-1e18,-1e18,0));
	return 0;
}
/*
5 
1 2 10 
1 3 40 
1 4 15 
1 5 20

10 
4 10 2 
1 2 21 
1 3 13 
6 7 1 
7 9 5 
2 4 3 
2 5 8 
1 6 55 
6 8 34

*/

Compilation message (stderr)

beads.cpp: In function 'void DP(int, int)':
beads.cpp:15:6: warning: unused variable 'ch' [-Wunused-variable]
  int ch = 0;
      ^~
beads.cpp: In function 'int main()':
beads.cpp:53:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
        ^
beads.cpp:53:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
          ^
beads.cpp:53:12: warning: unused variable 'l' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
            ^
beads.cpp:53:20: warning: unused variable 'd' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
                    ^
beads.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
beads.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a,&b,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~

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