이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int inf = 2e9;
int root;
int n;
vector<pair<int,int>> g[200005], f[200005];
pair<int,int> t[200005];
int dp[200005][2][2];
/**
Conditii:
- muchiile albastre sa fie de forma 2k
- pot alege k noduri si sa dau fiecaruia doua muchii albastre din set, pe care le voi orienta spre nodul respectiv
- sa nu existe doua noduri din cele k, astfel incat fiecare muchie din cele 4 orientate spre vreun nod din astea "se uita" si spre celalalt
Deci am un dp[nod][0/1][0/1] care reprezinta: suma costurilor max cu care pot face subarb lui nod, folosesc sau nu muchia nod--t[nod],
am sau nu am vreun nod albastru in subarbore pentru care ambele muchii care se uita spre el sa ii vina din fii?
**/
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);
}
}
}
/*
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)
{
if (f[nod].empty())
{
dp[nod][0][0] = 0;
dp[nod][0][1] = dp[nod][1][0] = dp[nod][1][1] = -inf;
return;
}
for (auto vecin : f[nod])
solve(vecin.first);
for (int j = 0; j < 2; j++)
for (int q = 0; q < 2; q++)
dp[nod][j][q] = -inf;
dp[nod][0][0] = 0;
for (auto vecin : f[nod])
dp[nod][0][0] += max(dp[vecin.first][0][0],dp[vecin.first][1][0]);
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][0],dp[fiu][1][0]);
d[i][1] = dp[fiu][0][0] + cost;
}
else
{
d[i][0] = d[i - 1][0] + max(dp[fiu][0][0],dp[fiu][1][0]);
d[i][1] = max(d[i - 1][1] + max(dp[fiu][0][0],dp[fiu][1][0]),d[i - 1][0] + dp[fiu][0][0] + cost);
}
}
dp[nod][1][0] = d[f[nod].size() - 1][1] + t[nod].second;
d.clear();
d.resize(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][0],dp[fiu][1][0]);
d[i][1] = max(dp[fiu][0][1],dp[fiu][1][1]);
}
else
{
d[i][0] = d[i - 1][0] + max(dp[fiu][0][0],dp[fiu][1][0]);
d[i][1] = max(d[i - 1][1] + max(dp[fiu][0][0],dp[fiu][1][0]),d[i - 1][0] + max(dp[fiu][0][1],dp[fiu][1][1]));
}
}
dp[nod][0][1] = d[f[nod].size() - 1][1];
vector<vector<vector<int>>> dd(f[nod].size());
for (int i = 0; i < f[nod].size(); i++)
{
dd[i].resize(3);
for (int j = 0; j < dd[i].size(); j++)
dd[i][j].resize(2);
}
for (int i = 0; i < f[nod].size(); i++)
for (int j = 0; j < 3; j++)
for (int q = 0; q < 2; q++)
dd[i][j][q] = -inf;
for (int i = 0; i < f[nod].size(); i++)
{
int fiu = f[nod][i].first,cost = f[nod][i].second;
if (i == 0)
{
dd[i][0][0] = max(dp[fiu][0][0],dp[fiu][1][0]);
dd[i][1][0] = cost + dp[fiu][0][0];
dd[i][1][1] = cost + dp[fiu][0][1];
}
else
{
dd[i][0][0] = dd[i - 1][0][0] + max(dp[fiu][0][0],dp[fiu][1][0]);
dd[i][1][0] = max(dd[i - 1][1][0] + max(dp[fiu][0][0],dp[fiu][1][0]),dd[i - 1][0][0] + cost + dp[fiu][0][0]);
dd[i][1][1] = max(dd[i - 1][1][1] + max(dp[fiu][0][0],dp[fiu][1][0]),dd[i - 1][0][0] + cost + dp[fiu][0][1]);
dd[i][2][0] = max(dd[i - 1][2][0] + max(dp[fiu][0][0],dp[fiu][1][0]),dd[i - 1][1][0] + cost + dp[fiu][0][0]);
dd[i][2][1] = max(dd[i - 1][2][1] + max(dp[fiu][0][0],dp[fiu][1][0]),dd[i - 1][1][0] + cost + dp[fiu][0][1]);
dd[i][2][1] = max(dd[i][2][1],dd[i - 1][1][1] + cost + dp[fiu][0][0]);
}
}
dp[nod][0][1] = max(dp[nod][0][1],max(dd[f[nod].size() - 1][2][0],dd[f[nod].size() - 1][2][1]));
d.clear();
d.resize(f[nod].size());
for (int i = 0; i < f[nod].size(); i++)
d[i].resize(2),d[i][0] = d[i][1] = -inf;
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][0],dp[fiu][1][0]);
d[i][1] = dp[fiu][0][1] + cost;
}
else
{
d[i][0] = d[i - 1][0] + max(dp[fiu][0][0],dp[fiu][1][0]);
d[i][1] = max(d[i - 1][1] + max(dp[fiu][0][0],dp[fiu][1][0]),d[i - 1][0] + dp[fiu][0][1] + cost);
}
}
dp[nod][1][1] = d[f[nod].size() - 1][1] + t[nod].second;
//cout << nod << ' ' << dp[nod][0][0] << ' ' << dp[nod][0][1] << ' ' << dp[nod][1][0] << ' ' << dp[nod][1][1] << endl;
}
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});
}
if (n == 2)
{
cout << 0;
return 0;
}
dfs(1);
solve(1);
cout << max(dp[1][0][0],dp[1][0][1]);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
beads.cpp: In function 'void solve(long long int)':
beads.cpp:68: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]
68 | for (int i = 0; i < f[nod].size(); i++)
| ~~^~~~~~~~~~~~~~~
beads.cpp:70: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]
70 | for (int i = 0; i < f[nod].size(); i++)
| ~~^~~~~~~~~~~~~~~
beads.cpp:88: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]
88 | for (int i = 0; i < f[nod].size(); i++)
| ~~^~~~~~~~~~~~~~~
beads.cpp:90: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]
90 | for (int i = 0; i < f[nod].size(); i++)
| ~~^~~~~~~~~~~~~~~
beads.cpp:92:35: warning: unused variable 'cost' [-Wunused-variable]
92 | int fiu = f[nod][i].first,cost = f[nod][i].second;
| ^~~~
beads.cpp:106: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]
106 | for (int i = 0; i < f[nod].size(); i++)
| ~~^~~~~~~~~~~~~~~
beads.cpp:109:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for (int j = 0; j < dd[i].size(); j++)
| ~~^~~~~~~~~~~~~~
beads.cpp:112: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]
112 | for (int i = 0; i < f[nod].size(); i++)
| ~~^~~~~~~~~~~~~~~
beads.cpp:116: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]
116 | for (int i = 0; i < f[nod].size(); i++)
| ~~^~~~~~~~~~~~~~~
beads.cpp:139: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]
139 | for (int i = 0; i < f[nod].size(); i++)
| ~~^~~~~~~~~~~~~~~
beads.cpp:141: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]
141 | 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... |