oj.uz

Submission #135062

# Submission time Handle Problem Language Result Execution time Memory
135062 2019-07-23T15:13:06 Z wilwxk Beads and wires (APIO14_beads) C++14
0 / 100
 6 ms 4984 KB 
#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(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;
	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

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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Incorrect 6 ms 4984 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Incorrect 6 ms 4984 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Incorrect 6 ms 4984 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Incorrect 6 ms 4984 KB Output isn't correct
5 Halted 0 ms 0 KB -