Submission #135060

#TimeUsernameProblemLanguageResultExecution timeMemory
135060wilwxkBeads and wires (APIO14_beads)C++14
0 / 100
6 ms4984 KiB
#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; 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); // 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", dp[raiz][0]); }

Compilation message (stderr)

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:48: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);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...