#include <bits/stdc++.h>
#define int long long
#define sz(x) (int)(x.size())
using namespace std;
const int LOG=12;
int n, m;
//LSONE
int LSOne(int i) {
return i&(-i);
}
//LCA
vector<vector<int>> child;
vector<vector<int>> up;
vector<int> depth;
void dfs(int s, int last=-1) {
for (auto u: child[s]) {
if (u==last) continue;
depth[u]=depth[s]+1;
up[u][0]=s;
for (int i=1; i<LOG; i++) {
up[u][i]=up[ up[u][i-1] ][ i-1 ];
}
dfs(u, s);
}
}
int getlca(int a, int b) {
if (a==b) return a;
if (depth[a] < depth[b]) swap(a, b);
int k = depth[a] - depth[b];
for (int j = LOG-1; j >= 0; j--) {
if (k & (1<<j)) {
a=up[a][j];
}
}
if (a==b) return a;
for (int j = LOG-1; j >= 0; j--) {
if (up[a][j] != up[b][j]) {
a=up[a][j];
b=up[b][j];
}
}
return up[a][0];
}
//DP
vector<vector<int>> memo;
vector<vector<pair<pair<int, int>, int>>> adj;
vector<vector<int>> val;
vector<vector<int>> memo2;
int dp(int s, int mask) {
if (__builtin_popcount(mask)>=child[s].size()) return 0;
if (memo[s][mask]!=-1) return memo[s][mask];
int ans=0;
for (auto u: child[s]) {
ans=max(ans, dp(u, 0));
}
for (auto u: adj[s]) {
int a=u.first.first, b=u.first.second, c=u.second;
int aa=a, bb=b;
if (mask&val[a][b]) continue;
if (memo2[a][b]!=-1) {
int sum=memo2[a][b];
ans=max(ans, sum+dp(s, (mask|val[a][b])));
continue;
}
int sum=c;
int prec=-1;
while (a!=s) {
int bitmask=0;
for (int i=0; i<sz(child[a]); i++) {
if (child[a][i]==prec) {
bitmask+=(1<<i);
}
}
sum+=dp(a, bitmask);
prec=a;
a=up[a][0];
}
prec=-1;
while (b!=s) {
int bitmask=0;
for (int i=0; i<sz(child[b]); i++) {
if (child[b][i]==prec) {
bitmask+=(1<<i);
}
}
sum+=dp(b, bitmask);
prec=b;
b=up[b][0];
}
memo2[aa][bb]=sum;
ans=max(ans, sum+dp(s, (mask|val[aa][bb])));
}
return memo[s][mask]=ans;
}
void solve() {
cin >> n >> m;
memo.clear();
memo.resize(n, vector<int>(1<<10+1, -1));
memo2.clear();
memo2.resize(n, vector<int>(n, -1));
val.clear();
val.resize(n, vector<int>(n));
adj.clear();
adj.resize(n);
child.clear();
child.resize(n);
up.clear();
up.resize(n, vector<int>(LOG));
depth.clear();
depth.resize(n);
vector<pair<pair<int, int>, int>> temp;
for (int i=0; i<m; i++) {
int u, v, c; cin >> u >> v >> c;
u--, v--;
if (c==0) {
child[u].push_back(v);
child[v].push_back(u);
} else {
temp.push_back({{u, v}, c});
}
}
depth[0]=0;
dfs(0);
for (int s=0; s<n; s++) {
for (int i=0; i<sz(child[s]); i++) {
auto u=child[s][i];
if (u==up[s][0]) {
child[s].erase(child[s].begin()+i);
}
}
}
int ans=0;
for (int i=n-1; i<m; i++) {
int u=temp[i-n+1].first.first, v=temp[i-n+1].first.second;
int c=temp[i-n+1].second;
int lca=getlca(u, v);
if (u!=v && (depth[u]+depth[v]-2*depth[lca])%2==0) {
adj[lca].push_back({{u, v}, c});
val[u][v]=0;
for (int j=0; j<sz(child[lca]); j++) {
auto s=child[lca][j];
if (getlca(s, u)==s || getlca(s, v)==s) {
val[u][v]+=(1<<j);
}
}
}
ans+=c;
}
cout << ans-dp(0, 0) << endl;
return;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tt=1;// cin >> tt;
while(tt--) solve();
return 0;
}
Compilation message
training.cpp: In function 'void solve()':
training.cpp:115:34: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
115 | memo.resize(n, vector<int>(1<<10+1, -1));
| ~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
32604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
32604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
32600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
