이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
if (st[3].size() == 1) {
dfs(v, u, na - max(dp[v][0], dp[v][1]), -0x3f3f3f3f);
continue;
}
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, -0x3f3f3f3f);
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:125: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:127: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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |