#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int LOG=31;
vector<vector<int>> paved;
vector<vector<int>> child;
vector<vector<pair<int,int>>> memo2;
vector<int> depth;
vector<vector<int>> parent;
vector<vector<pair<pair<int,int>,int>>> edges;
map<pair<int,int>,int> memo;
vector<vector<int>> memoLCA;
int lca(int a, int b){
if(depth[b]>depth[a]) swap(a,b);
int _a=a;
int _b=b;
if(memoLCA[a][b]!=-1) return memoLCA[_a][_b];
int k=depth[a]-depth[b];
for (int j = LOG-1; j >= 0; j--) if(k&(1<<j)) a=parent[a][j];
if(a==b) return memoLCA[_a][_b]=a;
for (int j = LOG-1; j >= 0; j--)
{
if(parent[a][j]!=parent[b][j]) {
a=parent[a][j];
b=parent[b][j];
}
}
return memoLCA[_a][_b]=parent[a][0];
}
int dp(int x, int mask){
if(memo.find({x,mask})!=memo.end()) return memo[{x,mask}];
if(child[x].size()==0) return memo[{x,mask}]=0;
int mx=0;
for (int i = 0; i < child[x].size(); i++)
{
if((mask&(1<<i))!=0) continue;
mx+=dp(child[x][i],0);
}
for(auto u : edges[x]) {
int a=u.first.first;
int b=u.first.second;
int c=u.second;
int d=(depth[a]+depth[b])-2*depth[x];
if(d%2!=0) continue;
int ap=a;
int bp=b;
if(memo2[a][b].first==-1){
int sum=0;
while(parent[ap][0]!=x&&ap!=x){
int bitmask=0;
for (int j = 0; j < child[parent[ap][0]].size(); j++)
{
if(child[parent[ap][0]][j]==ap) { bitmask+=(1<<j); break; }
}
sum+=dp(parent[ap][0],bitmask);
ap=parent[ap][0];
}
while(parent[bp][0]!=x&&bp!=x){
int bitmask=0;
for (int j = 0; j < child[parent[bp][0]].size(); j++)
{
if(child[parent[bp][0]][j]==bp) { bitmask+=(1<<j); break; }
}
sum+=dp(parent[bp][0],bitmask);
bp=parent[bp][0];
}
if(a!=x) sum+=dp(a,0);
if(b!=x) sum+=dp(b,0);
int bitmask=0;
for (int j = 0; j < child[x].size(); j++)
{
if(child[x][j]==ap||child[x][j]==bp) bitmask+=(1<<j);
}
memo2[a][b]={sum,bitmask};
}
if((memo2[a][b].second&mask)!=0) continue;
mx=max(mx,memo2[a][b].first+c+dp(x,memo2[a][b].second));
}
return memo[{x,mask}]=mx;
}
signed main() {
// Input:
ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>n>>m;
paved.resize(n+1);
depth.resize(n+1);
parent.resize(n+1, vector<int>(LOG, 0));
memoLCA.resize(n+1, vector<int>(n+1, -1));
memo2.resize(n+1, vector<pair<int,int>>(n+1,{-1,-1}));
edges.resize(n+1);
child.resize(n+1);
int sum=0;
vector<pair<pair<int,int>, int>> edgesTOPROCESS;
for (int i = 0; i < m; i++)
{
int a,b,c; cin >> a >> b >> c;
sum+=c;
if(a>b) swap(a,b);
if(c==0) {
paved[a].push_back(b);
paved[b].push_back(a);
}
else {
edgesTOPROCESS.push_back({{a,b},c});
}
}
queue<int> q;
q.push(1);
parent[1][0]=1;
depth[1]=0;
vector<bool> visited(n+1);
while(!q.empty()){
int x=q.front(); q.pop();
visited[x]=true;
for (auto u: paved[x])
{
if(visited[u]) continue;
q.push(u);
child[x].push_back(u);
parent[u][0]=x;
depth[u]=depth[x]+1;
}
}
for (int j = 1; j < LOG; j++) for (int i = 1; i <= n; i++) parent[i][j]=parent[parent[i][j-1]][j-1];
for (int i = 0; i < m-(n-1); i++)
{
int a=edgesTOPROCESS[i].first.first;
int b=edgesTOPROCESS[i].first.second;
int c=edgesTOPROCESS[i].second;
int d=(depth[a]+depth[b])-2*depth[lca(a,b)];
if(d%2!=0) continue;
edges[lca(a,b)].push_back({{a,b},c});
}
cout << sum-dp(1,0) << "\n";
return 0;
}
//MlogN + N*2^10 + M*3*N*10
Compilation message
training.cpp: In function 'long long int dp(long long int, long long int)':
training.cpp:40:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (int i = 0; i < child[x].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
training.cpp:57:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int j = 0; j < child[parent[ap][0]].size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
training.cpp:66:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int j = 0; j < child[parent[bp][0]].size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
training.cpp:76:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for (int j = 0; j < child[x].size(); j++)
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
477 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
24664 KB |
Output is correct |
| 2 |
Correct |
55 ms |
24916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
348 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
590 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
351 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
501 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
395 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
422 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
678 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
761 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
