Submission #906021

#	Time	Username	Problem	Language	Result	Execution time	Memory
906021		Alcabel	Training (IOI07_training)	C++17	100 / 100	11 ms	4728 KiB

training

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e3, maxchildren = 10;
vector<int> g[maxn], through[maxn];
int par[maxn], parIdx[maxn], h[maxn], tin[maxn], tout[maxn], tt;
vector<pair<int, int>> edges;
vector<int> w;

void dfsRoot(int v) {
    tin[v] = tt++;
    for (int i = 0; i < (int)g[v].size(); ++i) {
        int u = g[v][i];
        if (u != par[v]) {
            par[u] = v;
            parIdx[u] = i;
            h[u] = h[v] + 1;
            dfsRoot(u);
        } else {
            swap(g[v][i], g[v].back());
            g[v].pop_back();
            --i;
        }
    }
    tout[v] = tt++;
}

bool isAncestor(int v, int u) {
    return tin[v] <= tin[u] && tout[v] >= tout[u];
}

int dp[maxn][1 << maxchildren];

void dfsAns(int v) {
    for (const int& u : g[v]) {
        dfsAns(u);
    }
    int c = g[v].size();
    for (int mask = 0; mask < (1 << c); ++mask) {
        dp[v][mask] = 0;
        for (int i = 0; i < c; ++i) {
            if (mask & (1 << i)) {
                dp[v][mask] += dp[g[v][i]][(1 << g[g[v][i]].size()) - 1];
            }
        }
    }
    int m = through[v].size();
    for (int i = 0; i < m; ++i) {
        int cost = w[through[v][i]], u, sub = 0;
        u = edges[through[v][i]].first;
        if (u != v) {
            cost += dp[u][(1 << g[u].size()) - 1];
            while (par[u] != v) {
                int p = par[u];
                cost += dp[p][((1 << g[p].size()) - 1) ^ (1 << parIdx[u])];
                u = p;
            }
            sub |= (1 << parIdx[u]);
        }
        u = edges[through[v][i]].second;
        if (u != v) {
            cost += dp[u][(1 << g[u].size()) - 1];
            while (par[u] != v) {
                int p = par[u];
                cost += dp[p][((1 << g[p].size()) - 1) ^ (1 << parIdx[u])];
                u = p;
            }
            sub |= (1 << parIdx[u]);
        }
        for (int mask = (1 << c) - 1; mask >= 0; --mask) {
            if ((mask & sub) == sub) {
                dp[v][mask] = max(dp[v][mask], cost + dp[v][mask ^ sub]);
            }
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    int sumAll = 0;
    for (int i = 0; i < m; ++i) {
        int v, u, weight;
        cin >> v >> u >> weight;
        --v, --u;
        if (weight == 0) {
            g[v].emplace_back(u);
            g[u].emplace_back(v);
        } else {
            sumAll += weight;
            edges.emplace_back(v, u);
            w.emplace_back(weight);
        }
    }
    par[0] = parIdx[0] = -1;
    h[0] = 0;
    tt = 0;
    dfsRoot(0);
    for (int i = 0; i < (int)edges.size(); ++i) {
        int v = edges[i].first, u = edges[i].second;
        if (h[v] % 2 != h[u] % 2) {
            swap(edges[i], edges.back());
            swap(w[i], w.back());
            edges.pop_back();
            w.pop_back();
            --i;
            continue;
        }
        if (tin[v] > tin[u]) {
            swap(edges[i].first, edges[i].second);
            swap(v, u);
        }
        int lca = v;
        while (!isAncestor(lca, u)) {
            lca = par[lca];
        }
        through[lca].emplace_back(i);
    }
    dfsAns(0);
    cout << sumAll - dp[0][(1 << g[0].size()) - 1] << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9