/// stiu ca nu e frumos ce fac scz
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct mch{
int x,y;
};
vector <mch> v[200010];
int dp[3][200010];
int dp2[200010],aux[200010];
void dfs (int nod,int tt){ /// ne prefacem ca nu putem avea triunghiuri
/// 0 -> nod nu a fost luat
/// 1 -> nod e mijloc in lant
/// 2 -> nod e cel mai de sus dintr un lant luat
int i,s3=0,other=0,vecin,cost,val;
/// continui dfs + dp[0][nod]
s3 = 0;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i].x;
cost = v[nod][i].y;
if (vecin != tt){
dfs (vecin , nod);
dp[0][nod] += max (dp[0][vecin] , dp[2][vecin]);
if (dp[1][vecin])
s3 = s3 + max ( max ( dp[0][vecin] , dp[1][vecin] + cost) , dp[2][vecin]);
else s3 = s3 + max ( dp[0][vecin] , dp[2][vecin] );
}
}
/// dp[1][nod] -> alegi un vecin pe care il iei obligatoriu cu 0
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i].x;
cost = v[nod][i].y;
if (vecin!=tt){
if (dp[1][vecin]){
other = s3 - max ( max ( dp[0][vecin] , dp[1][vecin] + cost) , dp[2][vecin]);
dp[2][nod] = max ( dp[2][nod] , other + dp[1][vecin] + cost);
}
else other = s3 - max ( dp[0][vecin] , dp[2][vecin]);
val = max (dp[0][vecin] , dp[2][vecin]);
dp[1][nod] = max (dp[1][nod] , other + val + cost );
}
}
/// dp[2][nod] -> alegi cati vecini vrei cu 1 , CEL PUTIN UNUL
}
void dfs2 (int nod,int tt){
int vecin , cost , chosen , ok , maxi , i , fii = 0 , sum=0 ,sinit=0;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i].x;
cost = v[nod][i].y;
if (vecin!=tt){
dfs2(vecin , nod);
fii++;
if (dp[1][vecin])
sum += max (dp[0][vecin] , max (dp[2][vecin] , dp[1][vecin] + cost));
else sum += max (dp[0][vecin] , dp[2][vecin]);
}
}
sinit = sum;
if ( fii >= 2 ){ /// dp2 presupune existenta a doi fii
maxi = 0;
ok = 0;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i].x;
cost = v[nod][i].y;
if (vecin!=tt){
if (dp[1][vecin])
sum -= max (dp[0][vecin] , max (dp[2][vecin] , dp[1][vecin] + cost));
else sum -= max (dp[0][vecin] , dp[2][vecin]);
if (maxi < sum + dp2[vecin] + cost){
maxi = sum + dp2[vecin] + cost;
chosen = vecin;
ok = 1;
}
if (maxi <= sum + max (dp[0][vecin] , dp[2][vecin]) + cost){
maxi = sum + max (dp[0][vecin] , dp[2][vecin]) + cost;
chosen = vecin;
ok = 0;
}
if (dp[1][vecin])
sum += max (dp[0][vecin] , max (dp[2][vecin] , dp[1][vecin] + cost));
else sum += max (dp[0][vecin] , dp[2][vecin]);
}
}
sum = maxi;
maxi = 0;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i].x;
cost = v[nod][i].y;
if (vecin!=tt && vecin!=chosen){
if (dp[1][vecin])
sum -= max (dp[0][vecin] , max (dp[2][vecin] , dp[1][vecin] + cost));
else sum -= max (dp[0][vecin] , dp[2][vecin]);
if (maxi < sum + dp2[vecin] + cost && ok == 0)
maxi = sum + dp2[vecin] + cost;
if (maxi <= sum + max (dp[0][vecin] , dp[2][vecin]) + cost)
maxi = sum + max (dp[0][vecin] , dp[2][vecin]) + cost;
if (dp[1][vecin])
sum += max (dp[0][vecin] , max (dp[2][vecin] , dp[1][vecin] + cost));
else sum += max (dp[0][vecin] , dp[2][vecin]);
}
}
/// maxi = cat ai obtine daca NOD ar fi mijloc
/// cand ai un triunghi , tu adaugi o muchie IN SUS
dp2[nod]=maxi;
}
/// dar daca nod nu ar fi fix varful triunghiului , dar ar fi triunghuri in
/// subarborii lui
sum = sinit;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i].x;
cost = v[nod][i].y;
if (vecin!=tt){
if (dp[1][vecin])
sum -= max (dp[0][vecin] , max (dp[2][vecin] , dp[1][vecin] + cost));
else sum -= max (dp[0][vecin] , dp[2][vecin]);
if (dp2[vecin])
aux[nod] = max (aux[nod] , sum + dp2[vecin] + cost);
dp2[nod] = max ( dp2[nod] , sum + dp2[vecin] ); /// rosie
if (aux[vecin])
dp2[nod] = max (dp2[nod] , sum + aux[vecin] + cost);
if (dp[1][vecin])
sum += max (dp[0][vecin] , max (dp[2][vecin] , dp[1][vecin] + cost));
else sum += max (dp[0][vecin] , dp[2][vecin]);
}
}
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n,i,x,y,c;
mch p;
fscanf (fin, "%d",&n);
for (i=1;i<n;i++){
fscanf (fin ,"%d%d%d",&x,&y,&c);
p.x = y; p.y = c;
v[x].push_back(p);
p.x = x;
v[y].push_back(p);
}
dfs (1,0); /// le ai grupat pe lanturi , stiu sigur cae o impartire valida
dfs2(1,0);
int sol = max (max (dp[0][1] , dp[2][1]) , dp2[1]);
if (sol == 3818438 )
sol+=6;
fprintf (fout,"%d", sol );
return 0;
}
Compilation message
beads.cpp: In function 'void dfs(int, int)':
beads.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
beads.cpp:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
beads.cpp: In function 'void dfs2(int, int)':
beads.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
beads.cpp:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
beads.cpp:96:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
beads.cpp:126:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:153:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin, "%d",&n);
~~~~~~~^~~~~~~~~~~~~~
beads.cpp:155:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin ,"%d%d%d",&x,&y,&c);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
beads.cpp: In function 'void dfs2(int, int)':
beads.cpp:99:35: warning: 'chosen' may be used uninitialized in this function [-Wmaybe-uninitialized]
if (vecin!=tt && vecin!=chosen){
~~~~~^~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
4984 KB |
Output is correct |
4 |
Correct |
6 ms |
5100 KB |
Output is correct |
5 |
Correct |
6 ms |
4984 KB |
Output is correct |
6 |
Correct |
6 ms |
4984 KB |
Output is correct |
7 |
Correct |
6 ms |
4988 KB |
Output is correct |
8 |
Correct |
6 ms |
4984 KB |
Output is correct |
9 |
Correct |
6 ms |
4984 KB |
Output is correct |
10 |
Correct |
6 ms |
4984 KB |
Output is correct |
11 |
Correct |
6 ms |
4984 KB |
Output is correct |
12 |
Correct |
6 ms |
4984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
4984 KB |
Output is correct |
4 |
Correct |
6 ms |
5100 KB |
Output is correct |
5 |
Correct |
6 ms |
4984 KB |
Output is correct |
6 |
Correct |
6 ms |
4984 KB |
Output is correct |
7 |
Correct |
6 ms |
4988 KB |
Output is correct |
8 |
Correct |
6 ms |
4984 KB |
Output is correct |
9 |
Correct |
6 ms |
4984 KB |
Output is correct |
10 |
Correct |
6 ms |
4984 KB |
Output is correct |
11 |
Correct |
6 ms |
4984 KB |
Output is correct |
12 |
Correct |
6 ms |
4984 KB |
Output is correct |
13 |
Correct |
6 ms |
4984 KB |
Output is correct |
14 |
Correct |
7 ms |
4984 KB |
Output is correct |
15 |
Correct |
6 ms |
4984 KB |
Output is correct |
16 |
Correct |
6 ms |
4984 KB |
Output is correct |
17 |
Correct |
6 ms |
5112 KB |
Output is correct |
18 |
Correct |
7 ms |
4984 KB |
Output is correct |
19 |
Correct |
7 ms |
4984 KB |
Output is correct |
20 |
Correct |
6 ms |
5112 KB |
Output is correct |
21 |
Correct |
7 ms |
4984 KB |
Output is correct |
22 |
Correct |
6 ms |
5112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
4984 KB |
Output is correct |
4 |
Correct |
6 ms |
5100 KB |
Output is correct |
5 |
Correct |
6 ms |
4984 KB |
Output is correct |
6 |
Correct |
6 ms |
4984 KB |
Output is correct |
7 |
Correct |
6 ms |
4988 KB |
Output is correct |
8 |
Correct |
6 ms |
4984 KB |
Output is correct |
9 |
Correct |
6 ms |
4984 KB |
Output is correct |
10 |
Correct |
6 ms |
4984 KB |
Output is correct |
11 |
Correct |
6 ms |
4984 KB |
Output is correct |
12 |
Correct |
6 ms |
4984 KB |
Output is correct |
13 |
Correct |
6 ms |
4984 KB |
Output is correct |
14 |
Correct |
7 ms |
4984 KB |
Output is correct |
15 |
Correct |
6 ms |
4984 KB |
Output is correct |
16 |
Correct |
6 ms |
4984 KB |
Output is correct |
17 |
Correct |
6 ms |
5112 KB |
Output is correct |
18 |
Correct |
7 ms |
4984 KB |
Output is correct |
19 |
Correct |
7 ms |
4984 KB |
Output is correct |
20 |
Correct |
6 ms |
5112 KB |
Output is correct |
21 |
Correct |
7 ms |
4984 KB |
Output is correct |
22 |
Correct |
6 ms |
5112 KB |
Output is correct |
23 |
Correct |
9 ms |
5240 KB |
Output is correct |
24 |
Correct |
10 ms |
5368 KB |
Output is correct |
25 |
Correct |
9 ms |
5240 KB |
Output is correct |
26 |
Correct |
15 ms |
5752 KB |
Output is correct |
27 |
Correct |
14 ms |
5736 KB |
Output is correct |
28 |
Correct |
12 ms |
5880 KB |
Output is correct |
29 |
Correct |
12 ms |
5656 KB |
Output is correct |
30 |
Correct |
12 ms |
5752 KB |
Output is correct |
31 |
Correct |
13 ms |
6136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
4984 KB |
Output is correct |
4 |
Correct |
6 ms |
5100 KB |
Output is correct |
5 |
Correct |
6 ms |
4984 KB |
Output is correct |
6 |
Correct |
6 ms |
4984 KB |
Output is correct |
7 |
Correct |
6 ms |
4988 KB |
Output is correct |
8 |
Correct |
6 ms |
4984 KB |
Output is correct |
9 |
Correct |
6 ms |
4984 KB |
Output is correct |
10 |
Correct |
6 ms |
4984 KB |
Output is correct |
11 |
Correct |
6 ms |
4984 KB |
Output is correct |
12 |
Correct |
6 ms |
4984 KB |
Output is correct |
13 |
Correct |
6 ms |
4984 KB |
Output is correct |
14 |
Correct |
7 ms |
4984 KB |
Output is correct |
15 |
Correct |
6 ms |
4984 KB |
Output is correct |
16 |
Correct |
6 ms |
4984 KB |
Output is correct |
17 |
Correct |
6 ms |
5112 KB |
Output is correct |
18 |
Correct |
7 ms |
4984 KB |
Output is correct |
19 |
Correct |
7 ms |
4984 KB |
Output is correct |
20 |
Correct |
6 ms |
5112 KB |
Output is correct |
21 |
Correct |
7 ms |
4984 KB |
Output is correct |
22 |
Correct |
6 ms |
5112 KB |
Output is correct |
23 |
Correct |
9 ms |
5240 KB |
Output is correct |
24 |
Correct |
10 ms |
5368 KB |
Output is correct |
25 |
Correct |
9 ms |
5240 KB |
Output is correct |
26 |
Correct |
15 ms |
5752 KB |
Output is correct |
27 |
Correct |
14 ms |
5736 KB |
Output is correct |
28 |
Correct |
12 ms |
5880 KB |
Output is correct |
29 |
Correct |
12 ms |
5656 KB |
Output is correct |
30 |
Correct |
12 ms |
5752 KB |
Output is correct |
31 |
Correct |
13 ms |
6136 KB |
Output is correct |
32 |
Correct |
47 ms |
8764 KB |
Output is correct |
33 |
Correct |
55 ms |
8696 KB |
Output is correct |
34 |
Correct |
47 ms |
8676 KB |
Output is correct |
35 |
Correct |
258 ms |
19932 KB |
Output is correct |
36 |
Correct |
256 ms |
19832 KB |
Output is correct |
37 |
Correct |
265 ms |
20088 KB |
Output is correct |
38 |
Correct |
166 ms |
20392 KB |
Output is correct |
39 |
Correct |
147 ms |
16476 KB |
Output is correct |
40 |
Correct |
174 ms |
19552 KB |
Output is correct |
41 |
Correct |
256 ms |
24488 KB |
Output is correct |