#include <bits/stdc++.h>
using namespace std;
struct NonTreeEdge
{
int x,y,cost;
};
vector <NonTreeEdge> salut;
vector <int> arb[8005];
int niv[8005];
int fiu[8005],tata[8005];
int rmqTree[8005][14],q,prim[8005];
vector <int> fii[8005];
void dfs(int x,int dad)
{
int nr=0;
niv[x]=niv[dad]+1;
rmqTree[++q][0]=x;
prim[x]=q;
for (int i=0;i<arb[x].size();i++)
{
int nod = arb[x][i];
if (nod!=dad)
{
tata[nod]=x;
dfs(nod,x);
fii[x].push_back(nod);
fiu[nod]=nr;
nr++;
rmqTree[++q][0]=x;
}
}
}
int n;
int din[1005][5005];
int i,j,m;
vector <NonTreeEdge> mn[1005];
int lca(int x,int y)
{
if (x==y)
{
return x;
}
x=prim[x];
y=prim[y];
if (x>y)
{
swap(x,y);
}
int dif = y-x;
int k =log2(dif);
if (niv[rmqTree[x][k]]<niv[rmqTree[y-(1<<k)+1][k]])
{
return rmqTree[x][k];
}
return rmqTree[y-(1<<k)+1][k];
}
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(q);
int p = 1;
for (int j=1;j<=lg;j++)
{
for (i=1;i<=q;i++)
{
if (niv[rmqTree[i][j-1]]<niv[rmqTree[i+p][j-1]])
{
rmqTree[i][j]=rmqTree[i][j-1];
}
else
{
rmqTree[i][j]=rmqTree[i+p][j-1];
}
}
p=p*2;
}
int lim = (1<<11);
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:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for (int i=0;i<arb[x].size();i++)
| ~^~~~~~~~~~~~~~
training.cpp: In function 'int rasp(int, int)':
training.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int i=0;i<fii[rad].size();i++)
| ~^~~~~~~~~~~~~~~~
training.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<NonTreeEdge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i=0;i<mn[rad].size();i++)
| ~^~~~~~~~~~~~~~~
training.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int j=0;j<fii[rad].size();j++)
| ~^~~~~~~~~~~~~~~~
training.cpp:64:18: warning: unused variable 'p' [-Wunused-variable]
64 | int raspfv=0,p=1,nr=0;
| ^
training.cpp:64:22: warning: unused variable 'nr' [-Wunused-variable]
64 | int raspfv=0,p=1,nr=0;
| ^~
training.cpp: In function 'int main()':
training.cpp:186:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<NonTreeEdge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
186 | for (i=0;i<salut.size();i++)
| ~^~~~~~~~~~~~~
training.cpp:188:13: warning: unused variable 'x' [-Wunused-variable]
188 | int x= salut[i].x;
| ^
training.cpp:189:13: warning: unused variable 'y' [-Wunused-variable]
189 | int y = salut[i].y;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Correct |
1 ms |
852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
13012 KB |
Output is correct |
| 2 |
Correct |
9 ms |
13152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
6900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
13076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
6848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
13012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
