제출 #32030

#제출 시각아이디문제언어결과실행 시간메모리
32030minimario구슬과 끈 (APIO14_beads)C++14
57 / 100
45 ms5372 KiB
#include <bits/stdc++.h> using namespace std; #define f first #define s second const int MAX = 100005; typedef pair<int, int> pii; vector<pii> g[MAX]; int dp[MAX][2][2]; int max(int a, int b, int c) { return max(max(a, b), c); } int max(int a, int b, int c, int d) { return max(max(a, b), max(c, d)); } void dfs(int u, int p=-1, int len=-1) { for (pii i : g[u]) { if (i.f == p) { continue; } dfs(i.f, u, i.s); } int sum = 0, sum2 = 0; vector<pii> val0, val1; for (pii i : g[u]) { if (i.f == p) { continue; } sum += max(dp[i.f][0][0], dp[i.f][1][0]); val0.push_back({max(dp[i.f][0][0], dp[i.f][1][0]) - dp[i.f][0][0] - i.s, i.f}); val1.push_back({max(dp[i.f][0][0], dp[i.f][1][0]) - dp[i.f][0][1] - i.s, i.f}); } sort(val0.begin(), val0.end()); sort(val1.begin(), val1.end()); for (int i=0; i<min(2, (int)val0.size()); i++) { for (int j=0; j<min(2, (int)val1.size()); j++) { if (val0[i].s != val1[j].s) { dp[u][0][1] = max(dp[u][0][1], sum - val0[i].f - val1[j].f); } } } if (val0.size() >= 2) { dp[u][0][1] = max(dp[u][0][1], sum - val0[0].f - val0[1].f); } if (p != -1) { for (pii i : g[u]) { if (i.f == p) { continue; } dp[u][1][0] = max(dp[u][1][0], len + sum - max(dp[i.f][0][0], dp[i.f][1][0]) + dp[i.f][0][0] + i.s); dp[u][1][1] = max(dp[u][1][1], len + sum - max(dp[i.f][0][0], dp[i.f][1][0]) + dp[i.f][0][1] + i.s); } } dp[u][0][0] = sum; for (pii i : g[u]) { if (i.f == p) { continue; } dp[u][0][1] = max(dp[u][0][1], sum - max(dp[i.f][0][0], dp[i.f][1][0]) + max(dp[i.f][0][1], dp[i.f][1][1])); } // cout << u << " " << dp[u][0][0] << " " << dp[u][0][1] << " " << dp[u][1][0] << " " << dp[u][1][1] << endl; } int main() { // freopen("a.in", "r", stdin); // freopen("a.out", "w", stdout); int n; scanf("%d", &n); for (int i=0; i<n-1; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); g[u].push_back({v, w}); g[v].push_back({u, w}); } dfs(1); printf("%d\n", max(dp[1][0][0], dp[1][0][1], dp[1][1][0], dp[1][1][1])); }

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

beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:20:15: warning: unused variable 'sum2' [-Wunused-variable]
  int sum = 0, sum2 = 0;
               ^~~~
beads.cpp: In function 'int main()':
beads.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n);
         ~~~~~^~~~~~~~~~
beads.cpp:60:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v, w; scanf("%d %d %d", &u, &v, &w);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...