제출 #77024

#제출 시각아이디문제언어결과실행 시간메모리
77024samuelfgs96구슬과 끈 (APIO14_beads)C++11
0 / 100
8 ms7040 KiB
#include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define eb emplace_back using namespace std; typedef pair<int, int> pii; typedef long long ll; const int N = 212345; int dp[N][2], pai[N]; vector <pii> g[N]; void lul (int u, int pu) { for (auto v : g[u]) if (v.fi != pu) { pai[v.fi] = u; lul(v.fi, u); } } int solve (int u, int cor, int pu) { int &ans = dp[u][cor]; if (ans != -1) return ans; ans = -0x3f3f3f3f; if (cor == 0) { //os filhos podem ser qualquer coisa ans = 0; for (auto q : g[u]) { int v, w; tie(v, w) = q; if (v == pu) continue; ans += max(solve(v, 0, u), solve(v, 1, u) + w); } } else { //um filho tem que ser azul vector <int> st[3]; vector <int> xd; for (auto q : g[u]) { int v, w; tie(v, w) = q; if (v == pu) continue; st[0].pb(solve(v, 0, u)); st[1].pb(solve(v, 1, u) + w); st[2].pb(solve(v, 0, u) + w); xd.pb(v); } if (st[0].empty()) return ans; int best_id = 0, best = st[2][0] - max(st[0][0], st[1][0]); ans = 0; for (int i = 0; i < st[0].size(); i++) { int value = max(st[0][i], st[1][i]); int lucro = st[2][i] - value; if (lucro > best) { best = lucro; best_id = i; } } for (int i = 0; i < st[0].size(); i++) if (best_id == i) ans += st[2][i]; else ans += max(st[0][i], st[1][i]); } return ans; } int ans; void dfs (int u, int pu, int a, int b) { { int tmp = 0; for (auto q : g[u]) { int v, w; tie(v, w) = q; if (v == pu) tmp += max(a, b + w); else tmp += max(dp[v][0], dp[v][1] + w); } ans = max(ans, tmp); } int na = 0, nb = 0; for (auto q : g[u]) { int v, w; tie(v, w) = q; if (v == pu) na += max(a, b + w); else na += max(dp[v][0], dp[v][1] + w); } vector <pii> st[4]; int ct = 0; vector <int> xd; for (auto q : g[u]) { int v, w; tie(v, w) = q; if (v == pu) { st[0].eb(a, -1); st[1].eb(b + w, -1); st[2].eb(a + w, -1); st[3].eb(a + w - max(a, b + w), ct++); xd.pb(-1); } else { st[0].eb(dp[v][0], v); st[1].eb(dp[v][1] + w, v); st[2].eb(dp[v][0] + w, v); st[3].eb(dp[v][0] + w - max(dp[v][0], dp[v][1] + w), ct++); xd.pb(v); } } sort(st[3].rbegin(), st[3].rend()); for (int i = 0; i < st[3].size(); i++) nb += max(st[0][i].fi, st[1][i].fi); for (auto q : g[u]) { int v, w; tie(v, w) = q; if (v == pu) continue; int aqui = nb; aqui -= max(dp[v][0], dp[v][1] + w); int k = st[3][0].se; if (xd[st[3][0].se] == v) { //pegar o segundo k = st[3][1].se; } aqui -= max(st[0][k].fi, st[1][k].fi); aqui += st[2][k].fi; dfs(v, u, na - max(dp[v][0], dp[v][1] + w), aqui); } } int main (void) { int n; scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); g[u].eb(v, w); g[v].eb(u, w); } memset (dp, -1, sizeof dp); lul(1, 0); for (int i = 1; i <= n; i++) { solve(i, 0, pai[i]); solve(i, 1, pai[i]); } dfs(1, 0, 0, 0); cout << ans << endl; return 0; }

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

beads.cpp: In function 'int solve(int, int, int)':
beads.cpp:50:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < st[0].size(); i++) {
                   ~~^~~~~~~~~~~~~~
beads.cpp:58:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < st[0].size(); i++)
                   ~~^~~~~~~~~~~~~~
beads.cpp: In function 'void dfs(int, int, int, int)':
beads.cpp:103:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < st[3].size(); i++)
                  ~~^~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:121: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:123: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...