| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1042374 | ef10 | Training (IOI07_training) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
#define LL long long
struct edge {
int root;
vector<int> children;
int a;
int b;
int c;
};
struct node {
int p;
int d;
int i;
};
auto cmp = [](const edge& a, const edge& b) {
if (a.root < b.root) return true;
if (a.root > b.root) return false;
if (a.c < b.c) return true;
if (a.c > b.c) return false;
if (a.a < b.a) return true;
if (a.a > b.a) return false;
if (a.b < b.b) return true;
if (a.b > b.b) return false;
return false;
};
node A[1005];
int N, M;
vector<int> adj[1005];
vector<edge> edges;
LL dp[1005][1<<11];
bool done[1005][1<<11];
void findcommon(edge& e) {
node a = A[e.a];
node b = A[e.b];
if (a.d > b.d) {
node t;
t = a;
a = b;
b = t;
}
while (b.d > a.d) {
if (b.p == a.i) {
e.root = a.i;
e.children.push_back(b.i);
return;
}
b = A[b.p];
}
while (true) {
if (b.p == a.p) {
e.root = b.p;
e.children.push_back(b.i);
e.children.push_back(a.i);
return;
}
b = A[b.p];
a = A[a.p];
}
}
void solve(int r, int mask) {
if (done[r][mask]) return;
done[r][mask] = true;
if (mask == 0 || (__builtin_popcount(mask) == 1 && r != 0)) return;
LL res = 0;
for (int i = 0; i < adj[r].size(); i++) {
if (adj[r][i]==A[r].p) continue;
if ((mask & (1<<i)) == 0) continue;
int n = adj[r][i];
solve(n, ((1<<adj[n].size())-1));
res += dp[n][(1<<adj[n].size())-1];
}
//cout << r << "/" << mask << ", res: " << res << endl;
auto it = lower_bound(edges.begin(), edges.end(), edge(r,{},0,0,0), cmp);
while (it!= edges.end() && it->root == r) {
int cmask = 0;
for (auto c : it->children) {
auto ind = lower_bound(adj[r].begin(),adj[r].end(),c)-adj[r].begin();
cmask |= (1<<ind);
}
if ((cmask & mask) != cmask) {
it++;
continue;
}
bool visited[N]; memset(visited,0,sizeof(visited));
LL current = it->c;
for (int i = 0; i < 2; i++) {
int n = (i==0) ? it->a : it->b;
int p = -1;
while (n != r) {
int nmask = (1 << (adj[n].size())) - 1;
if (p>=0) {
auto indp = lower_bound(adj[n].begin(),adj[n].end(),p)-adj[n].begin();
nmask &= ~(1<<indp);
}
solve(n,nmask);
current += dp[n][nmask];
//cout << "1current + dp["<<n<<"]["<<nmask<<"] = " << dp[n][nmask] << endl;
visited[n] = true;
p = n;
n = A[n].p;
}
}
int rmask = mask & ~cmask;
solve(r,rmask);
current += dp[r][rmask];
//cout << "2current + dp["<<r<<"]["<<rmask<<"] = " << dp[r][rmask] << endl;
for (int i = 0; i < adj[r].size(); i++) {
if (adj[r][i] == A[r].p) continue;
if (!(rmask & (1<<i))) continue;
int n = adj[r][i];
if (visited[n]) continue;
solve(n,(1<<adj[n].size())-1);
current += dp[n][(1<<adj[n].size())-1];
}
//cout << r << "/" << mask << ", edge: " << it->a << "/" << it->b << "/" << it->c << ", current: " << current << endl;
if (current > res) {
res = current;
}
it++;
}
dp[r][mask] = res;
//cout << "dp["<<r<<"]["<<mask<<"] = " << res << endl;
}
void dfs(int r, int p) {
if (p >= 0) {
A[r].d = A[p].d + 1;
}
A[r].p = p;
for (auto e : adj[r]) {
if (e == p) continue;
dfs(e, r);
}
}
int main() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
A[i].i = i;
}
vector<edge> es;
LL totalc = 0;
for (int i = 0; i < M; i++) {
int a,b, c; cin >> a >> b >> c; a--; b--;
totalc += c;
if (c == 0) {
adj[a].push_back(b);
adj[b].push_back(a);
} else {
es.push_back(edge({-1,{},a,b,c}));
}
}
for (int i = 0; i < N; i++) {
sort(adj[i].begin(),adj[i].end());
}
dfs(0, -1);
for (auto e : es) {
if (((A[e.a].d + A[e.b].d) % 2) == 0) {
edges.push_back(e);
}
}
for (auto& e : edges) {
findcommon(e);
}
sort(edges.begin(),edges.end(), cmp);
solve(0, (1<<adj[0].size())-1);
cout << totalc-dp[0][(1<<adj[0].size())-1] << endl;
}