Submission #135280

#	Time	Username	Problem	Language	Result	Execution time	Memory
135280		wilwxk	Beads and wires (APIO14_beads)	C++14	13 / 100	7 ms	5112 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; //maior dp[viz][0]+peso- normal
	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) maior=val2;
	}
 
	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;
}
 
int main() {
	scanf("%d", &n);
	srand(time(0)+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<=100; i++) {
		int cur=rand()%n+1;
		dfs(cur, cur);
		respf=max(respf, dp[cur][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:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:44: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: 13 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43