제출 #15859

#제출 시각아이디문제언어결과실행 시간메모리
15859myungwoo구슬과 끈 (APIO14_beads)C++14
100 / 100
441 ms41100 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 200005 #define pb push_back #define sz(v) ((int)(v).size()) int N; int D[MAXN], E[MAXN]; int up[MAXN], par[MAXN], V[MAXN]; int ans; vector <int> con[MAXN], conv[MAXN], tcon[MAXN]; void dp(int n, int from) { vector <int> arr; for (int i=sz(con[n]);i--;){ int t = con[n][i], v = conv[n][i]; if (t == from) continue; up[t] = v; par[t] = n; dp(t, n); arr.pb(t); } D[n] = E[n] = 0; for (int t: arr){ V[t] = max(D[t], E[t]); D[n] += V[t]; } for (int t: arr) E[n] = max(E[n], D[n] - V[t] + D[t] + up[t] + up[n]); tcon[n] = arr; } void dfs(int n, int d, int e) { int v = max(d, e), sum = D[n] + v; ans = max(ans, sum); int mx1 = -2e9, mx1t, mx2 = -2e9; if (par[n]) mx1 = -v + d + up[n], mx1t = 0; for (int t: tcon[n]){ int val = -V[t] + D[t] + up[t]; if (mx1 <= val) mx2 = mx1, mx1 = val, mx1t = t; else if (mx2 < val) mx2 = val; } for (int t: tcon[n]){ int nxt_d = sum - max(D[t], E[t]); dfs(t, nxt_d, mx1t == t ? nxt_d + mx2 + up[t] : nxt_d + mx1 + up[t]); } } int main() { scanf("%d", &N); for (int i=1;i<N;i++){ int a, b, c; scanf("%d%d%d", &a, &b, &c); con[a].pb(b); conv[a].pb(c); con[b].pb(a); conv[b].pb(c); } dp(1, 0); dfs(1, 0, 0); printf("%d\n", ans); }

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

beads.cpp: In function 'int main()':
beads.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
beads.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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...