#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define sz(a) (int)a.size()
#define int long long
using namespace std;
using PII = pair <int, int>;
const int N = 1001; // maxNode
const int M = 5001; // maxEdge
const int K = 11; // max power of 2 to N, number of children
int n, m;
// solution helper
int cost[M], dp[N][1<<K], lcas[M];
map <int, int> edgeID[N];
vector <PII> edges;
vector <int> intersectingEdges[N];
vector <PII> edgeChildren[M]; // pos, state of children
// lca
int lvl[N];
int jump[N][K+1];
vector <int> paths[N];
void dfs(int pos, int par = 1) {
jump[pos][0] = par;
for (auto& el : paths[pos]) {
if (el == par) continue;
lvl[el] = lvl[pos]+1;
dfs(el, pos);
}
}
int Jump(int a, int b) {
for (int j = 0; j < K; j++)
if (b & (1<<j)) a = jump[a][j];
return a;
}
int LCA(int a, int b) {
if (lvl[a] < lvl[b]) swap(a, b);
a = Jump(a, lvl[a]-lvl[b]);
if (a == b) return a;
for (int j = K-1; j >= 0; j--) {
if (jump[a][j] != jump[b][j]) {
a = jump[a][j];
b = jump[b][j];
}
}
return jump[a][0];
}
string binStr(int s, int p) {
string res = "";
while(s > 0) {
res = res+string(1, ((s&1) + '0'));
s /= 2;
}
while(res.size() < sz(paths[p])) res+="0";
while(res.size() < 4) res +=".";
return res;
}
int solve(int pos, int mask = 0) {
if (pos != 1) mask |= (1<<edgeID[pos][jump[pos][0]]);
int& res = dp[pos][mask];
if (res != -1) return res;
res = 0;
for (int i = 0; i < sz(paths[pos]); i++) {
if (mask & (1<<i)) continue;
res = solve(paths[pos][i]);
}
for (auto& intersect : intersectingEdges[pos]) {
// check if already blocked
bool blocked = 0;
for (int j = sz(edgeChildren[intersect])-2; j < sz(edgeChildren[intersect]); j++) {
if (mask & (1<<edgeChildren[intersect][j].ss)) blocked = 1;
}
if (blocked) continue;
int cur = cost[intersect];
for (int j = 0; j < sz(edgeChildren[intersect])-2; j++) {
PII tmp = edgeChildren[intersect][j];
int newMask = (1<<tmp.ss);
cur += solve(tmp.ff, newMask);
}
int newMask = mask;
for (int j = sz(edgeChildren[intersect])-2; j < sz(edgeChildren[intersect]); j++) {
newMask |= 1<<edgeChildren[intersect][j].ss;
}
cur += solve(pos, newMask);
if (lcas[intersect] != edges[intersect].ff) cur += solve(edges[intersect].ff);
if (lcas[intersect] != edges[intersect].ss) cur += solve(edges[intersect].ss);
res = max(res, cur);
}
// cout << pos << " " << binStr(mask, pos) << ": " << res << '\n';
return res;
}
signed main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// freopen("0.in", "r", stdin);
// freopen("0.out", "w", stdout);
cin >> n >> m;
int mustBlock = 0, sum = 0;
for (int i = 1; i <= m; i++) {
int a, b, c; cin >> a >> b >> c;
if (!c) {
edgeID[a][b] = sz(paths[a]); paths[a].pb(b);
edgeID[b][a] = sz(paths[b]); paths[b].pb(a);
} else {
cost[sz(edges)] = c;
edges.pb({a, b});
}
}
dfs(1);
for (int j = 1; j < K; j++)
for (int i = 1; i <= n; i++)
jump[i][j] = jump[jump[i][j-1]][j-1];
for (int i = 0; i <= m-n; i++) {
int a, b; tie(a, b) = edges[i];
if (lvl[a]%2 != lvl[b]%2) {
edges[i] = {-1, -1};
mustBlock += cost[i];
continue;
}
sum += cost[i];
int lca = LCA(a, b), p;
lcas[i] = lca;
if (lvl[a] < lvl[b]) swap(a, b);
while(lvl[jump[a][0]] > lvl[lca]) {
p = jump[a][0];
edgeChildren[i].pb({p, edgeID[p][a]});
a = p;
}
while(lvl[jump[b][0]] > lvl[lca]) {
p = jump[b][0];
edgeChildren[i].pb({p, edgeID[p][b]});
b = p;
}
if (b == lca) b = a;
p = jump[a][0];
edgeChildren[i].pb({p, edgeID[p][a]});
p = jump[b][0];
edgeChildren[i].pb({p, edgeID[p][b]});
intersectingEdges[lca].pb(i);
// for (auto [a, b] : edgeChildren[i]) cout << a << "," << b << ',' << paths[a][b] << " "; cout << "\n";
}
memset(dp, -1, sizeof(dp));
cout << mustBlock + sum - solve(1) << '\n';
}
Compilation message
training.cpp: In function 'std::string binStr(long long int, long long int)':
training.cpp:59:19: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
59 | while(res.size() < sz(paths[p])) res+="0";
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
16596 KB |
Output is correct |
| 2 |
Correct |
7 ms |
16468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
16596 KB |
Output is correct |
| 2 |
Correct |
7 ms |
16596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
24040 KB |
Output is correct |
| 2 |
Correct |
31 ms |
24828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
16596 KB |
Output is correct |
| 2 |
Correct |
7 ms |
16468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
16596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
16520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
16724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
17108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
18456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
26124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
