제출 #135257

#제출 시각아이디문제언어결과실행 시간메모리
135257pedro_sponchiado구슬과 끈 (APIO14_beads)C++17
0 / 100
15 ms14456 KiB
#include<bits/stdc++.h> using namespace std; const int maxn=200000; const int INF=1000000000; int n; vector<int> adj[maxn], peso[maxn]; int dp1[maxn], dp2[maxn]; int marc[maxn]; vector<pair<int, int> > filhos[maxn]; vector<int> aux; void dfs(int u, int p_ar_ant){ marc[u]=1; int folha=1; for(int i=0; i<adj[u].size(); i++){ int v=adj[u][i]; if(marc[v]==0){ folha=0; dfs(v, peso[u][i]); filhos[u].push_back(make_pair(dp1[v]+peso[u][i], max(dp1[v], dp2[v]))); } } if(folha){ dp1[u]=0; dp2[u]=-INF; return; } int t=filhos[u].size(); int s=0; for(int i=0; i<t; i++) s+=filhos[u][i].second; //calcula dp1[u] if(t>=2){ dp1[u]=-INF; for(int i=0; i<t; i++){ for(int k=i+1; k<t; k++){ int aux1=s-filhos[u][i].second-filhos[u][k].second + filhos[u][i].first+filhos[u][k].first; dp1[u]=max(dp1[u], aux1); } } } else dp1[u]=s; //calcula dp2[u] if(p_ar_ant!=-1){ dp2[u]=-INF; for(int i=0; i<t; i++){ int aux1=s-filhos[u][i].second+filhos[u][i].first; dp2[u]=max(dp2[u], aux1); } dp2[u]+=p_ar_ant; } return; } int main(){ scanf("%d", &n); for(int a, b, p, i=1; i<=n-1; i++){ scanf("%d %d %d", &a, &b, &p); adj[a].push_back(b); adj[b].push_back(a); peso[a].push_back(p); peso[b].push_back(p); } dfs(1, -1); /* printf("\n\n"); for(int i=1; i<=n; i++){ printf("%d: %d %d\n", i, dp1[i], dp2[i]); } */ printf("%d\n", dp1[1]); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:18:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<adj[u].size(); i++){
               ~^~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a, &b, &p);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...