이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n) { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
#define BitCount(x) __builtin_popcount(x)
using namespace std;
typedef long long LL;
typedef pair <int, int> II;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n;
int f[N], p[N], a[N];
int dp[N][5];
vector <II> adj[N];
void DFS(int u, int par = -1) {
f[u] = -INF;
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first, w = adj[u][k].second;
if (v == par) continue;
f[u] = max(f[u], w);
p[v] = u; a[v] = w;
DFS(v, u);
}
}
void DP(int u) {
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first, w = adj[u][k].second;
if (v == p[u]) continue;
DP(v);
}
FOR(i, 0, 4) dp[u][i] = 0;
// dp[u][0]
int S = 0;
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first, w = adj[u][k].second;
if (v == p[u]) continue;
S += max(dp[v][1], dp[v][3]);
}
II best1 = II(-INF, -1), best2 = II(-INF, -1);
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first, w = adj[u][k].second;
if (v == p[u]) continue;
int value = -max(dp[v][1], dp[v][3]) + w + dp[v][3];
if (best1 == II(-INF, -1)) best1 = II(value, v);
else if (best2 == II(-INF, -1)) {
if (best1.first < value) {
best2 = best1;
best1 = II(value, v);
} else best2 = II(value, v);
} else {
best2 = II(value, v);
if (best1.first < best2.first) swap(best1, best2);
}
}
REP(k1, 0, adj[u].size()) {
int v1 = adj[u][k1].first, w1 = adj[u][k1].second;
if (v1 == p[u]) continue;
/*REP(k2, 0, adj[u].size()) if (k1 != k2) {
int v2 = adj[u][k2].first, w2 = adj[u][k2].second;
if (v2 == p[u]) continue;
int newS = S - max(dp[v1][1], dp[v1][3]) - max(dp[v2][1], dp[v2][3]);
dp[u][0] = max(dp[u][0], newS + w1 + w2 + dp[v1][3]
+ max(dp[v2][0], dp[v2][4]));
}*/
dp[u][0] = max(dp[u][0], S - max(dp[v1][1], dp[v1][3]) + w1 + max(dp[v1][0], dp[v1][4])
+ (best1.second == v1 ? best2.first : best1.first));
}
//dp[u][1]
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first, w = adj[u][k].second;
if (v == p[u]) continue;
int newS = S - max(dp[v][1], dp[v][3]);
dp[u][1] = max(dp[u][1], newS + dp[v][3] + w + a[u]);
}
// dp[u][2]
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first, w = adj[u][k].second;
if (v == p[u]) continue;
int newS = S - max(dp[v][1], dp[v][3]);
dp[u][2] = max(dp[u][2], newS + max(dp[v][0], dp[v][4]) + w + a[u]);
}
// dp[u][3]
dp[u][3] = S;
// dp[u][4]
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first, w = adj[u][k].second;
if (v == p[u]) continue;
int newS = S - max(dp[v][1], dp[v][3]);
int val = 0;
FOR(i, 0, 4) val = max(val, dp[v][i]);
dp[u][4] = max(dp[u][4], val + newS);
}
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // LOCAL
scanf("%d", &n);
FOR(i, 1, n - 1) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
adj[u].push_back(II(v, w));
adj[v].push_back(II(u, w));
}
DFS(1);
DP(1);
printf("%d", max(dp[1][0], max(dp[1][3], dp[1][4])));
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
beads.cpp: In function 'void DFS(int, int)':
beads.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
beads.cpp:27:9:
REP(k, 0, adj[u].size()) {
~~~~~~~~~~~~~~~~~~~
beads.cpp:27:5: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^~~
beads.cpp: In function 'void DP(int)':
beads.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
beads.cpp:37:9:
REP(k, 0, adj[u].size()) {
~~~~~~~~~~~~~~~~~~~
beads.cpp:37:5: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^~~
beads.cpp:38:34: warning: unused variable 'w' [-Wunused-variable]
int v = adj[u][k].first, w = adj[u][k].second;
^
beads.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
beads.cpp:45:9:
REP(k, 0, adj[u].size()) {
~~~~~~~~~~~~~~~~~~~
beads.cpp:45:5: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^~~
beads.cpp:46:34: warning: unused variable 'w' [-Wunused-variable]
int v = adj[u][k].first, w = adj[u][k].second;
^
beads.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
beads.cpp:51:9:
REP(k, 0, adj[u].size()) {
~~~~~~~~~~~~~~~~~~~
beads.cpp:51:5: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^~~
beads.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
beads.cpp:66:9:
REP(k1, 0, adj[u].size()) {
~~~~~~~~~~~~~~~~~~~~
beads.cpp:66:5: note: in expansion of macro 'REP'
REP(k1, 0, adj[u].size()) {
^~~
beads.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
beads.cpp:82:9:
REP(k, 0, adj[u].size()) {
~~~~~~~~~~~~~~~~~~~
beads.cpp:82:5: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^~~
beads.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
beads.cpp:90:9:
REP(k, 0, adj[u].size()) {
~~~~~~~~~~~~~~~~~~~
beads.cpp:90:5: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^~~
beads.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
beads.cpp:101:9:
REP(k, 0, adj[u].size()) {
~~~~~~~~~~~~~~~~~~~
beads.cpp:101:5: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^~~
beads.cpp:102:34: warning: unused variable 'w' [-Wunused-variable]
int v = adj[u][k].first, w = adj[u][k].second;
^
beads.cpp: In function 'int main()':
beads.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
beads.cpp:118:27: 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... |