제출 #135280

#제출 시각아이디문제언어결과실행 시간메모리
135280wilwxk구슬과 끈 (APIO14_beads)C++14
13 / 100
7 ms5112 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; 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); }

컴파일 시 표준 에러 (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);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...