Submission #57254

#	Time	Username	Problem	Language	Result	Execution time	Memory
57254		Plurm	Beads and wires (APIO14_beads)	C++11	0 / 100	6 ms	4992 KiB

beads

#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long ll;
const int MXN = 2e5+5;
vector<pair<int,int> > g[MXN];
ll dp[MXN][2];
void dfs(int c,int p = -1){
	ll s = 0ll;
	for(int i = 0; i < g[c].size(); i++){
		pair<int,int> x = g[c][i];
		if(x.first == p) continue;
		dfs(x.first,c);
		s += max(dp[x.first][0],dp[x.first][1] + (ll)x.second);
	}
	ll m = s;
	for(int i = 0; i < g[c].size(); i++){
		if(g[c][i].first == p) continue;
		for(int j = i+1; j < g[c].size(); j++){
			if(g[c][j].first == p) continue;
			m = max(m,s 
				- max(dp[g[c][i].first][0],dp[g[c][i].first][1] + (ll)g[c][i].second)
				- max(dp[g[c][j].first][0],dp[g[c][j].first][1] + (ll)g[c][j].second) 
				+ dp[g[c][i].first][0]
				+ g[c][i].second
				+ dp[g[c][j].first][0]
				+ g[c][j].second
				);
		}
	}
	dp[c][0] = m;
	m = -1e16;
	for(int i = 0; i < g[c].size(); i++){
		if(g[c][i].first == p) continue;
		m = max(m,s + dp[g[c][i].first][0] + (ll)g[c][i].second
			- max(dp[g[c][i].first][0],dp[g[c][i].first][1] + (ll)g[c][i].second));
	}
	dp[c][1] = m;
}
int main(){
	#ifdef REDIRECT_IO
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	int n;
	scanf("%d",&n);
	if(n > 1000) throw 0;
	int a,b,c;
	for(int i = 1; i < n; i++){
		scanf("%d%d%d",&a,&b,&c);
		g[a].eb(b,c);
		g[b].eb(a,c);
	}
	dfs(1);
	printf("%lld",dp[1][0]);
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:10:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[c].size(); i++){
                 ~~^~~~~~~~~~~~~
beads.cpp:17:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[c].size(); i++){
                 ~~^~~~~~~~~~~~~
beads.cpp:19:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = i+1; j < g[c].size(); j++){
                    ~~^~~~~~~~~~~~~
beads.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[c].size(); i++){
                 ~~^~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
beads.cpp:50: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: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43