#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
const int cox[4] = {1, 0, -1, 0};
const int coy[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 7, pr = 31;
const int mxn = 1e3 + 5, mxs = 3e5 * 50, sq = 500, mxv = 2e6 + 1;
const int max_iter = 8e4, global_iter = 15e5 + 5;
//const int base = (1 <<18);
const ll inf = 1e9 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct E{
int u, v, w;
};
int n, m;
int dep[mxn + 1], up[mxn + 1][11], mask[mxn + 1][mxn + 1], pa[mxn + 1];
int dp[mxn + 1][(1 << 10)];
vt<int>adj[mxn + 1];
vt<E>edge, queries[mxn + 1];
void ckmax(int &a, int b){
if(a < b)a = b;
}
void prep(int s, int pre){
for(auto i: adj[s]){
if(i != pre){
dep[i] = dep[s] + 1; up[i][0] = pa[i] = s;
prep(i, s);
}
}
}
int lca(int u, int v){
if(dep[u] < dep[v])swap(u, v);
int k = dep[u] - dep[v];
for(int i = 0; i < 11; i++){
if((k >> i) & 1)u = up[u][i];
}
if(u == v)return(u);
for(int i = 10; i >= 0; i--){
if(up[u][i] != up[v][i]){
u = up[u][i]; v = up[v][i];
}
}
return(up[u][0]);
}
void dfs(int s, int pre){
for(auto i: adj[s]){
if(i != pre){
dfs(i, s);
}
}
for(int i = 0; i < (1 << sz(adj[s])); i++){
for(int j = 0; j < sz(adj[s]); j++){
if((i >> j) & 1){
if(adj[s][j] != pre){
int son = adj[s][j];
dp[s][i] += dp[son][(1 << sz(adj[son])) - 1];
}
}
}
}
//dp[i][j] node i used mask j
for(auto [u, v, w]: queries[s]){
int tot = 0, ms = 0;
while(u != s){
tot += dp[u][((1 << sz(adj[u])) - 1) ^ ms]; ms = mask[pa[u]][u];
if(pa[u] == s)break;
u = pa[u];
}
ms = 0;
while(v != s){
tot += dp[v][((1 << sz(adj[v])) - 1) ^ ms]; ms = mask[pa[v]][v];
if(pa[v] == s)break;
v = pa[v];
}
int add = mask[s][u] | mask[s][v];
for(int j = ((1 << sz(adj[s])) - 1); j >= 0; j--){
if((j & add) == 0){
ckmax(dp[s][j | add], dp[s][j] + tot + w);
}
}
}
}
void solve(){
cin >> n >> m;
int tot = 0;
for(int i = 0; i < m; i++){
int a, b, c; cin >> a >> b >> c;
if(c == 0){
adj[a].pb(b); adj[b].pb(a);
}else{
edge.pb({a, b, c}); tot += c;
}
}
for(int i = 1; i <= n; i++){
for(int j = 0; j < sz(adj[i]); j++){
mask[i][adj[i][j]] = (1 << j);
}
}
prep(1, -1);
for(int i = 1; i < 11; i++){
for(int j = 1; j <= n; j++){
up[j][i] = up[up[j][i - 1]][i - 1];
}
}
for(auto [u, v, w]: edge){
if((dep[u] & 1) == (dep[v] & 1)){
queries[lca(u, v)].pb({u, v, w});
}
}
dfs(1, -1);
cout << tot - dp[1][((1 << sz(adj[1])) - 1)];
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("KHONG.inp", "r", stdin);
//freopen("KHONG.out", "w", stdout);
int tt; tt = 1;
while(tt--)solve();
return(0);
}
Compilation message
training.cpp: In function 'void dfs(int, int)':
training.cpp:79:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
79 | for(auto [u, v, w]: queries[s]){
| ^
training.cpp: In function 'void solve()':
training.cpp:122:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
122 | for(auto [u, v, w]: edge){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5140 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
7 ms |
6668 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8688 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7012 KB |
Output is correct |
| 2 |
Correct |
8 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
6 ms |
8464 KB |
Output is correct |
| 4 |
Correct |
6 ms |
6748 KB |
Output is correct |
