# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 5005;
int t,n,m,a[N],in[N],out[N],tin, dp[N][1025],id[N][N];
int par[N],lv[N];
vector <int> v[N];
void dfs(int a, int p) {
in[a] = ++tin;
par[a] = p;
lv[a] = lv[p] + 1;
for (int to : v[a]) {
if (to == p) continue;
dfs(to, a);
}
out[a] = tin;
}
int upper(int a, int b) {
return (in[a] <= in[b] && out[a] >= out[b]);
}
int lca(int a, int b) {
int cur = a;
while (!upper(cur, b)) {
cur = par[cur];
}
return cur;
}
int get(int a, int p) {
int cur = a, lst = -1, ans = 0;
while (cur != p) {
if (lst == -1) ans += dp[cur][0];
else ans += dp[cur][id[cur][lst]];
lst = cur;
cur = par[cur];
}
return ans;
}
vector <array <int, 3> > g[N];
int kth(int x, int k) {
while (k--) {
x = par[x];
}
return x;
}
void dfs1(int a, int p) {
int cnt = 0;
for (int to : v[a]) {
if (to == p) continue;
id[a][to] = cnt;
cnt++;
dfs1(to, a);
}
vector <array <int, 4> > pot;
for (array <int, 3> edge : g[a]) {
int x = edge[0], y = edge[1], z = edge[2];
int msk = 0;
if (a != x) {
int getx = kth(x, lv[x] - lv[a] - 1);
msk |= (1<<id[a][getx]);
}
if (a != y) {
int gety = kth(y, lv[y] - lv[a] - 1);
msk |= (1<<id[a][gety]);
}
pot.pb({x, y, z, msk});
}
for (array <int, 4> edge : pot) {
int x = edge[0], y = edge[1], z = edge[2], cur_mask = edge[3];
for (int msk = (1<<cnt) - 1; msk >= 0; msk--) {
if ((msk & cur_mask)) continue;
int cur_pas = dp[a][msk | cur_mask]; // add (x -- y) wibo
cur_pas += get(x, a) + get(y, a) + z;
dp[a][msk] = max(dp[a][msk], cur_pas);
}
}
}
main() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
vector < array <int, 3 > > vec, vn;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin>>a>>b>>c;
if (c == 0) {
v[a].pb(b);
v[b].pb(a);
} else {
vec.pb({a, b, c});
}
}
dfs(1, 0);
for (array <int, 3> x : vec) {
int a = x[0], b = x[1], c = x[2];
int dist = lv[a] + lv[b] - 2 * lv[lca(a, b)];
if (dist % 2 == 1) {
} else vn.pb(x);
}
vec = vn;
for (array <int, 3> x : vec) {
int a = x[0], b = x[1], c = x[2];
g[lca(a, b)].pb({a,b,c});
}
dfs1(1, 0);
cout<<dp[1][0]<<"\n";
}
Compilation message
training.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
84 | main() {
| ^~~~
training.cpp: In function 'int main()':
training.cpp:100:27: warning: unused variable 'c' [-Wunused-variable]
100 | int a = x[0], b = x[1], c = x[2];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
8 ms |
6612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
2 ms |
1364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
4436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
3936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
