이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int inf = 2e9;
int n;
vector<pair<int,int>> g[200005], f[200005];
pair<int,int> t[200005];
int dp[200005][2];
void dfs(int nod)
{
for (auto vecin : g[nod])
{
if (vecin.first != t[nod].first)
{
f[nod].push_back(vecin);
t[vecin.first] = {nod,vecin.second};
dfs(vecin.first);
}
}
}
void calc_dp0(int nod)
{
vector<vector<int>> d(f[nod].size());
for (int i = 0; i < f[nod].size(); i++)
d[i].resize(3);
for (int i = 0; i < f[nod].size(); i++)
{
int fiu = f[nod][i].first,cost = f[nod][i].second;
if (i == 0)
{
d[i][2] = -inf;
d[i][0] = max(dp[fiu][0],dp[fiu][1]);
d[i][1] = dp[fiu][0] + cost;
}
else
{
d[i][0] = d[i - 1][0] + max(dp[fiu][0],dp[fiu][1]);
d[i][1] = max(d[i - 1][0] + dp[fiu][0] + cost,d[i - 1][1] + max(dp[fiu][0],dp[fiu][1]));
d[i][2] = max(d[i - 1][1] + dp[fiu][0] + cost,d[i - 1][2] + max(dp[fiu][0],dp[fiu][1]));
}
}
dp[nod][0] = max(d[f[nod].size() - 1][0],d[f[nod].size() - 1][2]);
}
void calc_dp1(int nod)
{
vector<vector<int>> d(f[nod].size());
for (int i = 0; i < f[nod].size(); i++)
d[i].resize(2);
for (int i = 0; i < f[nod].size(); i++)
{
int fiu = f[nod][i].first,cost = f[nod][i].second;
if (i == 0)
{
d[i][0] = max(dp[fiu][0],dp[fiu][1]);
d[i][1] = dp[fiu][0] + cost;
}
else
{
d[i][0] = d[i - 1][0] + max(dp[fiu][0],dp[fiu][1]);
d[i][1] = max(d[i - 1][0] + dp[fiu][0] + cost,d[i - 1][1] + max(dp[fiu][0],dp[fiu][1]));
}
}
dp[nod][1] = d[f[nod].size() - 1][1] + t[nod].second;
}
/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/
void solve(int nod)
{
for (auto vecin : f[nod])
solve(vecin.first);
if (f[nod].size() == 0)
{
dp[nod][0] = 0;
dp[nod][1] = -inf;
return;
}
calc_dp0(nod);
if (nod != 1)
calc_dp1(nod);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 1; i < n; i++)
{
int x,y,z;
cin >> x >> y >> z;
g[x].push_back({y,z});
g[y].push_back({x,z});
}
dfs(1);
solve(1);
cout << dp[1][0];
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
beads.cpp: In function 'void calc_dp0(long long int)':
beads.cpp:30:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i = 0; i < f[nod].size(); i++)
| ~~^~~~~~~~~~~~~~~
beads.cpp:32:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int i = 0; i < f[nod].size(); i++)
| ~~^~~~~~~~~~~~~~~
beads.cpp: In function 'void calc_dp1(long long int)':
beads.cpp:54:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int i = 0; i < f[nod].size(); i++)
| ~~^~~~~~~~~~~~~~~
beads.cpp:56:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i = 0; i < f[nod].size(); i++)
| ~~^~~~~~~~~~~~~~~
# | 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... |