Submission #135071

#	Time	Username	Problem	Language	Result	Execution time	Memory
135071		wilwxk	Beads and wires (APIO14_beads)	C++14	0 / 100	6 ms	4984 KiB

beads

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=2e5+5;
const ll INF=1e18;
vector<pair<int, ll> > g[MAXN];
ll dp[MAXN][2];
int n;
ll respf;

void dfs(int cur, int p) {
	dp[cur][0]=0; dp[cur][1]=0;

	ll maior=-INF, maior2=-INF; //maior dp[viz][0]+peso- normal
	ll soma=0;
	for(auto aresta : g[cur]) {
		int viz; ll peso; tie(viz, peso)=aresta;
		if(viz==p) continue;
		dfs(viz, cur);

		ll val=max(dp[viz][1]+peso, dp[viz][0]);
		dp[cur][1]+=val;

		ll val2=dp[viz][0]+peso;
		val2-=val;
		if(val2>=maior) maior2=maior, maior=val2;
		else if(val2>maior2) maior2=val2;
	
		soma+=dp[viz][0];
	}

	if(cur!=p&&g[cur].size()==1) {
		dp[cur][0]=0;
		dp[cur][1]=-INF;
		return;
	}

	//os dois estao com soma de max(dp(i, 1)+p, dp(i, 0))
	dp[cur][0]=dp[cur][1];
	dp[cur][1]+=maior;
	if(maior+maior2>0) dp[cur][0]+=(maior+maior2);
	dp[cur][0]=max(dp[cur][0], soma);
}

int main() {
	scanf("%d", &n);
	for(int i=0; i<n-1; i++) {
		int a, b, c; scanf("%d %d %d", &a, &b, &c);
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}

	int raiz=1; for(int i=1; i<=n; i++) if(g[i].size()!=1) raiz=i;
	dfs(raiz, raiz);
	respf=dp[raiz][0];

	for(int i=1; i<=n; i++) dfs(i, i), respf=max(respf, dp[i][0]);
	// for(int i=1; i<=n; i++) printf("%d: %lld %lld\n", i, dp[i][0], dp[i][1]);

	if(n<=2) printf("0\n");
	else printf("%lld\n", respf);
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:49:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b, c; scanf("%d %d %d", &a, &b, &c);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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