제출 #50797

#제출 시각아이디문제언어결과실행 시간메모리
50797waynetuinfor구슬과 끈 (APIO14_beads)C++17
28 / 100
1068 ms24192 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; const long long inf = 1e15; vector<pair<int, int>> gr[maxn]; long long dp[3][maxn]; void dfs(int x, int p) { dp[0][x] = 0; dp[1][x] = dp[2][x] = -inf; for (auto u : gr[x]) if (u.first != p) { dfs(u.first, x); dp[0][x] += max(dp[1][u.first] + u.second, max(dp[2][u.first], dp[0][u.first])); } for (auto u : gr[x]) if (u.first != p) { long long t = max(dp[1][u.first] + u.second, max(dp[2][u.first], dp[0][u.first])); dp[1][x] = max(dp[1][x], dp[0][x] - t + u.second + max(dp[2][u.first], dp[0][u.first])); } /* for (int i = 0; i < gr[x].size(); ++i) if (gr[x][i].first != p) { for (int j = 0; j < gr[x].size(); ++j) if (gr[x][j].first != p) { int a = gr[x][i].first, b = gr[x][j].first; int c = gr[x][i].second, d = gr[x][j].second; if (a == b) continue; long long y = max(dp[1][a] + c, max(dp[2][a], dp[0][a])); long long z = max(dp[1][b] + d, max(dp[2][b], dp[0][b])); dp[2][x] = max(dp[2][x], dp[0][x] - y - z + c + max(dp[2][a], dp[0][a]) + d + max(dp[2][b], dp[0][b])); } } */ } int main() { int n; scanf("%d", &n); for (int i = 0; i < n - 1; ++i) { int a, b, c; scanf("%d %d %d", &a, &b, &c); gr[a].emplace_back(b, c); gr[b].emplace_back(a, c); } long long ans = -inf; for (int i = 1; i <= n; ++i) { dfs(i, 0); ans = max(ans, dp[0][i]); } printf("%lld\n", ans); return 0; }

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

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