제출 #1003300

#제출 시각아이디문제언어결과실행 시간메모리
1003300BF001구슬과 끈 (APIO14_beads)C++17
0 / 100
2 ms4956 KiB
#include <bits/stdc++.h> using namespace std; #define N 200005 #define int long long #define fi first #define se second typedef pair<int, int> ii; int n, dp[3][N], res = 0, wi[N], mm[N]; vector<ii> adj[N]; bool cmp(int& a, int& b){ return a > b; } void dfs(int u, int p){ int d1 = 0, d2 = 0, ma = -1e15; vector<int> tmp; for (auto x : adj[u]){ int v = x.fi, w = x.se; if (v == p) continue; dfs(v, u); if (dp[0][v] > 0){ dp[1][u] += max(dp[0][v] + w, dp[1][v]); } else dp[1][u] += dp[1][v]; if (dp[0][v] > 0){ dp[0][u] += dp[0][v] + w; ma = max(ma, dp[1][v] - dp[0][v]); } else ma = max(ma, dp[1][v] + w); wi[v] = w; } dp[0][u] += ma; mm[u] = ma; } void ud(int p0, int p1, int v){ int cst = p1; if (p0 > 0) cst = max(cst, p0 + wi[v]); dp[1][v] += cst; } void rr(int u, int p, int p0, int p1){ res = max(res, dp[1][u]); int siz = adj[u].size() - (p != 0); vector<int> pre(siz + 2, 0), suf(siz + 2, 0), mpre(siz + 2, 0), msuf(siz + 2, 0); mpre[0] = -1e15, msuf[siz + 1] = -1e15; if (p != 0){ if (p0 > 0){ pre[0] += p0 + wi[u]; mpre[0] = p1 - p0; } else mpre[0] = p1 + wi[u]; } int pos = 0; for (auto x : adj[u]){ int v = x.fi, w = x.se; if (v == p) continue; pos++; pre[pos] = pre[pos - 1]; mpre[pos] = mpre[pos - 1]; if (dp[0][v] > 0){ pre[pos] += dp[0][v] + w; mpre[pos] = max(mpre[pos], dp[1][v] - dp[0][v]); } else mpre[pos] = max(mpre[pos], dp[1][v] + w); } pos = siz + 1; for (int i = adj[u].size() - 1; i >= 0; i--){ int v = adj[u][i].fi, w = adj[u][i].se; if (v == p) continue; pos--; suf[pos] = suf[pos + 1]; msuf[pos] = msuf[pos + 1]; if (dp[0][v] > 0){ suf[pos] += dp[0][v] + w; msuf[pos] = max(msuf[pos], dp[1][v] - dp[0][v]); } else msuf[pos] = max(msuf[pos], dp[1][v] + w); } pos = 0; for (auto x : adj[u]){ int v = x.fi, w = x.se; if (v == p) continue; int cst = dp[1][v]; pos++; if (dp[0][v] > 0) cst = max(cst, dp[0][v] + w); int p1 = dp[1][u] - cst; int p0 = pre[pos - 1] + suf[pos + 1] + max(mpre[pos - 1], msuf[pos + 1]); ud(p0, p1, v); rr(v, u, p0, p1); } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cin >> n; for (int i = 1; i <= n - 1; i++){ int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } int root = 1; dfs(root, 0); rr(root, 0, 0, 0); cout << res; return 0; }

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

beads.cpp: In function 'void dfs(long long int, long long int)':
beads.cpp:19:6: warning: unused variable 'd1' [-Wunused-variable]
   19 |  int d1 = 0, d2 = 0, ma = -1e15;
      |      ^~
beads.cpp:19:14: warning: unused variable 'd2' [-Wunused-variable]
   19 |  int d1 = 0, d2 = 0, ma = -1e15;
      |              ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...