#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int p[N][20], tmin[N], tmout[N], timer, UP[N], h[N];
vector<int> t[N];
vector<int> x[N];
vector<pair<pii,int >> E[N];
bool check(int u, int v) {
return (tmin[u] <= tmin[v] && tmout[u] >= tmout[v]);
}
int lca(int u, int v) {
if(check(u, v)) return u;
if(check(v, u)) return v;
for(int i = 16; i >= 0; i--) {
if(p[u][i] && !check(p[u][i], v)) u = p[u][i];
}
return p[u][0];
}
void dfs1(int u, int P) {
tmin[u] = ++timer;
p[u][0] = P; h[u] = h[P] + 1;
for(int i = 1; i <= 16; i++) p[u][i] = p[p[u][i - 1]][i - 1];
for(int i = 0; i < t[u].size(); i++) {
if(t[u][i] == P) continue;
UP[t[u][i]] = 1 << i;
p[t[u][i]][0] = u;
dfs1(t[u][i], u);
}
tmout[u] = timer;
}
int get(int u) {
return x[u][(1 << t[u].size()) - 1];
}
int up(int a, int u) {
int ans = (a == u ? 0 : get(a));
vector<int> v;
while(a != u) {
v.push_back(a);
a = p[a][0];
}
for(int i = 1; i < v.size(); i++) {
ans = max(ans, x[v[i]][((1 << (int)t[v[i]].size()) - 1) ^ UP[v[i - 1]]]);
}
return ans;
}
int get(int l, int a, int b) {
int x = 0;
for(int i = 0; i < t[l].size(); i++) {
if(t[l][i] != p[l][0] && check(t[l][i], a)) x += 1 << i;
if(t[l][i] != p[l][0] && check(t[l][i], b)) x += 1 << i;
}
return x;
}
void dfs(int u, int p) {
for(int i = 0; i < t[u].size(); i++) {
if(t[u][i] == p) continue;
dfs(t[u][i], u);
}
x[u].resize(1 << (int)t[u].size());
for(int j = 0; j < E[u].size(); j++) {
int a = E[u][j].f.f, b = E[u][j].f.s, c = E[u][j].s;
c += up(a, u) + up(b, u);
int bb = get(u, a, b);
assert(up(a, u) >= 0); assert(up(b, u) >= 0);
for(int mask = (1 << (int)t[u].size()) - 1; mask >= 0; --mask) {
if(!(mask & bb))
x[u][mask + bb] = max(x[u][mask + bb], x[u][mask] + c);
}
}
for(int mask = 0; mask < (1 << (int)t[u].size()); ++mask) {
int cur = x[u][mask];
for(int i = 0; i < t[u].size(); i++) {
if(t[u][i] == p) continue;
if(!(mask& (1 << i))) x[u][mask ^ (1 << i)] = max(x[u][mask ^ (1 << i)] , x[u][mask] + get(t[u][i]));
}
}
}
main(){
int n, m, cost = 0;
cin >> n >> m;
vector<pair<pii,int> > e;
for(int i = 1; i <= m; i++) {
int u, v, c;
cin >> u >> v >> c;
if(!c) t[u].push_back(v), t[v].push_back(u);
else e.push_back({{u, v}, c});
cost += c;
}
int root = 1;
dfs1(root, 0);
for(int i = 0; i < e.size(); ++i) {
int u = e[i].f.f, v = e[i].f.s, c = e[i].s;
if((h[u] + h[v]) % 2 == 1) continue;
E[lca(u, v)].push_back({{u, v}, c});
}
dfs(root, 0);
cout << cost - get(root) << endl;
}
Compilation message
training.cpp: In function 'void dfs1(long long int, long long int)':
training.cpp:28:22: 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]
28 | for(int i = 0; i < t[u].size(); i++) {
| ~~^~~~~~~~~~~~~
training.cpp: In function 'long long int up(long long int, long long int)':
training.cpp:46:22: 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]
46 | for(int i = 1; i < v.size(); i++) {
| ~~^~~~~~~~~~
training.cpp: In function 'long long int get(long long int, long long int, long long int)':
training.cpp:54:22: 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]
54 | for(int i = 0; i < t[l].size(); i++) {
| ~~^~~~~~~~~~~~~
training.cpp: In function 'void dfs(long long int, long long int)':
training.cpp:61:22: 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]
61 | for(int i = 0; i < t[u].size(); i++) {
| ~~^~~~~~~~~~~~~
training.cpp:66:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int j = 0; j < E[u].size(); j++) {
| ~~^~~~~~~~~~~~~
training.cpp:78:26: 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]
78 | for(int i = 0; i < t[u].size(); i++) {
| ~~^~~~~~~~~~~~~
training.cpp:77:13: warning: unused variable 'cur' [-Wunused-variable]
77 | int cur = x[u][mask];
| ^~~
training.cpp: At global scope:
training.cpp:85:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
85 | main(){
| ^~~~
training.cpp: In function 'int main()':
training.cpp:99:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i = 0; i < e.size(); ++i) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14464 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
14792 KB |
Output is correct |
| 2 |
Correct |
19 ms |
14776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
14676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
14932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
15060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
15028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
