제출 #32025

#제출 시각아이디문제언어결과실행 시간메모리
32025minimario구슬과 끈 (APIO14_beads)C++14
0 / 100
4 ms2688 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]; 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; vector<int> subtract; for (pii i : g[u]) { if (i.f == p) { continue; } sum += max(dp[i.f][0], dp[i.f][1]); subtract.push_back(max(dp[i.f][0], dp[i.f][1]) - i.s - dp[i.f][0]); } sort(subtract.begin(), subtract.end()); if (subtract.size() >= 2) { dp[u][0] = sum - subtract[0] - subtract[1]; } if (p != -1) { for (pii i : g[u]) { if (i.f == p) { continue; } dp[u][1] = max(dp[u][1], sum + len + i.s - max(dp[i.f][0], dp[i.f][1]) + dp[i.f][0]); } } dp[u][0] = max(dp[u][0], sum); // cout << u << " " << dp[u][0] << " " << dp[u][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], dp[1][1])); }

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

beads.cpp: In function 'int main()':
beads.cpp:40: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:42: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...