| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 507839 |
2022-01-13T04:02:21 Z |
8e7 |
Training (IOI07_training) |
C++17 |
|
34 ms |
27484 KB |
//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary (T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#define ll long long
#define maxn 1005
#define maxc 10
#define maxm 5005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> adj[maxn], pnt[maxn], path[maxn];
pii ed[maxm], chi[maxm];
int w[maxm], pa[maxn], dep[maxn];
void dfs(int n, int par, int d) {
dep[n] = d;
pa[n] = par;
for (int v:adj[n]) {
if (v != par) {
dfs(v, n, d + 1);
}
}
}
int ans = 0;
int tot, dp[maxn][maxm], id[maxn], best[maxn];
void solve(int n, int par) {
int d = 0, sum = 0;
for (int v:adj[n]) {
if (v != par) {
solve(v, n);
sum += best[v];
id[v] = d++;
}
}
for (int i:pnt[n]) chi[i] = {0, 0};
for (int v:adj[n]) {
for (int j:path[v]) {
if (!chi[j].ff) chi[j].ff = v;
else chi[j].ss = v;
}
}
vector<int> bit(1<<d, sum);
for (int i:pnt[n]) {
auto [u, v] = chi[i];
int se = 0, val = 0;
if (u) se += 1<<id[u], val += dp[u][i] - best[u];
if (v) se += 1<<id[v], val += dp[v][i] - best[v];
//debug(i, chi[i].ff, chi[i].ss, se,val);
for (int j = 0;j < (1<<d);j++) {
if ((j & se) == 0) {
bit[j | se] = max(bit[j | se], bit[j] + w[i] + val);
}
}
}
for (int i = 1;i < (1<<d);i++) {
for (int j = 0;j < d;j++) {
if (i & (1<<j)) bit[i] = max(bit[i], bit[i ^ (1<<j)]);
}
}
ans = max(ans, bit[(1<<d) - 1]);
best[n] = bit[(1<<d) - 1];
for (int i = 1;i <= tot;i++) dp[n][i] = best[n];
for (int v:adj[n]) {
if (v == par) continue;
for (int i:path[v]) {
dp[n][i] = bit[(1<<d) - 1 - (1<<id[v])] - best[v] + dp[v][i];
}
}
//debug(n, best[n]);
//pary(bit.begin(), bit.end());
//debug(n, dp[n][7]);
}
int main() {
io
int n, m;
cin >> n >> m;
tot = m;
int tc = 0;
for (int i = 1;i <= m;i++) {
int u, v;
cin >> u >> v >> w[i];
tc += w[i];
if (w[i] == 0) {
adj[u].push_back(v);
adj[v].push_back(u);
} else {
ed[i] = {u, v};
}
}
dfs(1, 0, 0);
int even = 0;
for (int i = 1;i <= m;i++) {
if (w[i]) {
auto [u, v] = ed[i];
if (dep[u] < dep[v]) swap(u, v);
int len = 0;
while (dep[u] > dep[v]) len++, path[u].push_back(i), u = pa[u];
while (u != v) {
path[u].push_back(i), path[v].push_back(i);
len += 2;
u = pa[u], v = pa[v];
}
if (len % 2 == 0) pnt[u].push_back(i);
else even += w[i], tc -= w[i];
}
}
/*
for (int i = 1;i <= n;i++) {
debug("path", i);
pary(path[i].begin(), path[i].end());
debug("pnt");
pary(pnt[i].begin(), pnt[i].end());
}
*/
solve(1, 0);
//debug(tc, even, ans);
cout << tc - ans + even << endl;
}
/*
9 12
1 2 0
1 3 0
3 4 0
3 5 0
5 6 0
5 7 0
5 8 0
8 9 0
7 8 3
6 8 5
2 6 4
4 9 6
7 10
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
1 5 3
2 6 5
3 5 2
5 7 7
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
588 KB |
Output is correct |
| 2 |
Correct |
1 ms |
648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
19872 KB |
Output is correct |
| 2 |
Correct |
23 ms |
21444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
844 KB |
Output is correct |
| 2 |
Correct |
1 ms |
844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2508 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7244 KB |
Output is correct |
| 3 |
Correct |
6 ms |
6988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
20548 KB |
Output is correct |
| 2 |
Correct |
13 ms |
20376 KB |
Output is correct |
| 3 |
Correct |
13 ms |
20444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6348 KB |
Output is correct |
| 2 |
Correct |
7 ms |
7952 KB |
Output is correct |
| 3 |
Correct |
31 ms |
26984 KB |
Output is correct |
| 4 |
Correct |
8 ms |
8492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
22476 KB |
Output is correct |
| 2 |
Correct |
34 ms |
27484 KB |
Output is correct |
| 3 |
Correct |
23 ms |
22492 KB |
Output is correct |
| 4 |
Correct |
14 ms |
20352 KB |
Output is correct |
