#include <bits/stdc++.h>
using namespace std;
struct NonTreeEdge
{
int x,y,cost;
};
vector <NonTreeEdge> salut;
vector <int> arb[1005];
int niv[1005];
int rmq[1005][12],fiu[1005],tata[1005];
vector <int> fii[1005];
void dfs(int x,int dad)
{
int nr=0;
niv[x]=niv[dad]+1;
for (int i=0;i<arb[x].size();i++)
{
int nod = arb[x][i];
if (nod!=dad)
{
tata[nod]=x;
rmq[nod][0]=x;
dfs(nod,x);
fii[x].push_back(nod);
fiu[nod]=nr;
nr++;
}
}
}
int n;
int lca(int x,int y)
{
if (niv[x]<niv[y])
{
return lca(y,x);
}
int dif = niv[x]-niv[y];
int lg = log2(n);
for (int i=0;i<=lg;i++)
{
if (dif&(1<<i))
{
x=rmq[x][i];
}
}
if (x!=y)
{
for (int i=lg;i>=1;i--)
{
if (rmq[x][i]!=rmq[y][i])
{
x=rmq[x][i];
y=rmq[y][i];
}
}
x=rmq[x][0];
}
return x;
}
int din[1005][5005];
int i,j,m;
vector <NonTreeEdge> mn[1005];
int rasp (int rad, int mask)
{
if (din[rad][mask]!=-1)
{
return din[rad][mask];
}
int raspfv=0,p=1,nr=0;
for (int i=0;i<fii[rad].size();i++)
{
if ((mask&(1<<i)))
{
continue;
}
raspfv= raspfv + rasp(fii[rad][i],0);
}
din[rad][mask]=raspfv;
for (int i=0;i<mn[rad].size();i++)
{
int x=mn[rad][i].x;
int y=mn[rad][i].y;
int cost = mn[rad][i].cost;
int varf = lca(x,y);
int copx=x,cop=y;
int p=1,ok=1;
for (int j=0;j<fii[rad].size();j++)
{
if (mask&p)
{
if (lca(x,fii[rad][j])==fii[rad][j]||lca(y,fii[rad][j])==fii[rad][j])
{
ok=0;
break;
}
}
p=p*2;
}
if (ok==0)
{
continue;
}
int sum=0;
varf = lca(x,y);
if (y==varf)
{
swap(x,y);
}
if (x==varf)
{
sum=sum+rasp(y,0)+cost;
cop=y;
while (cop!=x)
{
sum=sum+rasp(tata[cop],(1<<fiu[cop]));
cop=tata[cop];
}
}
else
{
sum=sum+rasp(y,0)+rasp(x,0)+cost;
cop=y;
while (tata[cop]!=varf)
{
sum=sum+rasp(tata[cop],(1<<fiu[cop]));
cop=tata[cop];
}
copx=x;
while (tata[copx]!=varf)
{
sum=sum+rasp(tata[copx],(1<<fiu[copx]));
copx=tata[copx];
}
sum=sum+rasp(varf,(1<<fiu[copx])+(1<<fiu[cop]));
}
din[rad][mask]=max(din[rad][mask],sum);
}
return din[rad][mask];
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0);
#ifdef HOME
ifstream cin("date.in");
ofstream cout("date.out");
#endif // HOME
cin>>n>>m;
int lastv=0;
for (int i=1;i<=m;i++)
{
int x,y,tip;
cin>>x>>y>>tip;
if (tip==0)
{
arb[x].push_back(y);
arb[y].push_back(x);
}
else
{
salut.push_back({x,y,tip});
lastv+=tip;
}
}
dfs(1,0);
int lg = log2(n);
for (i=1;i<=lg;i++)
{
for (j=1;j<=n;j++)
{
rmq[j][i]=rmq[rmq[j][i-1]][i-1];
}
}
int lim = (1<<10);
for (i=1;i<=n;i++)
{
for (j=0;j<lim;j++)
{
din[i][j]=-1;
}
}
for (i=0;i<salut.size();i++)
{
int x= salut[i].x;
int y = salut[i].y;
int ceau =lca (salut[i].x,salut[i].y);
if ((niv[salut[i].x]+niv[salut[i].y]-2*niv[ceau])%2==1)
{
continue;
}
mn[ceau].push_back(salut[i]);
}
cout<<lastv-rasp(1,0);
return 0;
}
Compilation message
training.cpp: In function 'void dfs(int, int)':
training.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (int i=0;i<arb[x].size();i++)
| ~^~~~~~~~~~~~~~
training.cpp: In function 'int rasp(int, int)':
training.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (int i=0;i<fii[rad].size();i++)
| ~^~~~~~~~~~~~~~~~
training.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<NonTreeEdge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i=0;i<mn[rad].size();i++)
| ~^~~~~~~~~~~~~~~
training.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int j=0;j<fii[rad].size();j++)
| ~^~~~~~~~~~~~~~~~
training.cpp:70:18: warning: unused variable 'p' [-Wunused-variable]
70 | int raspfv=0,p=1,nr=0;
| ^
training.cpp:70:22: warning: unused variable 'nr' [-Wunused-variable]
70 | int raspfv=0,p=1,nr=0;
| ^~
training.cpp: In function 'int main()':
training.cpp:183:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<NonTreeEdge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
183 | for (i=0;i<salut.size();i++)
| ~^~~~~~~~~~~~~
training.cpp:185:13: warning: unused variable 'x' [-Wunused-variable]
185 | int x= salut[i].x;
| ^
training.cpp:186:13: warning: unused variable 'y' [-Wunused-variable]
186 | int y = salut[i].y;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1089 ms |
724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1089 ms |
8664 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1080 ms |
468 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1070 ms |
1108 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
2900 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1080 ms |
4564 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
8788 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1087 ms |
4436 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1085 ms |
8660 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
