Submission #679873

#	Time	Username	Problem	Language	Result	Execution time	Memory
679873		lorenzoferrari	Training (IOI07_training)	C++17	30 / 100	9 ms	704 KiB

training

/*
 *  First of all, bicolor the tree. Any admissible unpaved edges must connect
 *  vertexes of the same colour.
 *
 *  Consider each unpaved edge (a, b) the path a->...->b on the tree. A simple
 *  even cycles exist iff an edge is traversed by two or more paths.
 *
 *  Find the maximal sum of a edge-disjoint subset of the given paths.
 *
 *  dp[v][0] is the maximal sum of edge-disjoint paths in the subtree of v;
 *  dp[v][1] also comprehend the edge (v, par[v])
 */

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

struct Lca {
    static constexpr int LOG = 10;
    int n;
    vector<int> dep;
    vector<vector<int>> up;

    Lca(int _n, const vector<vector<int>>& adj) : n(_n) {
        dep.assign(n, 0);
        up.assign(n, vector<int>(LOG));
        auto dfs = [&](auto&& self, int v, int p) -> void {
            up[v][0] = p;
            for (int u : adj[v]) {
                if (u == p) continue;
                dep[u] = dep[v] + 1;
                self(self, u, v);
            }
        };
        dfs(dfs, 0, 0);
        for (int i = 1; i < LOG; ++i) {
            for (int j = 0; j < n; ++j) {
                up[j][i] = up[up[j][i-1]][i-1];
            }
        }
    }

    int lift(int v, int k) const {
        for (int i = LOG-1; i >= 0; --i) {
            if (k & (1 << i)) {
                v = up[v][i];
            }
        }
        return v;
    }

    vector<int> get_dep() const { return dep; }
    vector<int> get_par() const {
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            ans[i] = up[i][0];
        }
        return ans;
    }

    int operator()(int a, int b) const {
        if (dep[a] > dep[b]) {
            swap(a, b);
        }
        b = lift(b, dep[b] - dep[a]);
        if (a == b) {
            return a;
        }
        for (int i = LOG-1; i >= 0; --i) {
            if (up[a][i] != up[b][i]) {
                a = up[a][i];
                b = up[b][i];
            }
        }
        return up[a][0];
    }
};

int main() {
    int n; cin >> n;
    int m; cin >> m;
    vector<array<int, 3>> e;
    vector<vector<int>> adj(n);
    for (int i = 0, a, b, c; i < m; ++i) {
        cin >> a >> b >> c; --a, --b;
        if (c) {
            e.push_back({a, b, c});
        } else {
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
    }
    Lca lca(n, adj);
    auto dep = lca.get_dep();
    auto par = lca.get_par();
    vector<vector<array<int, 3>>> paths(n);
    for (auto [a, b, c] : e) {
        if ((dep[a] & 1) == (dep[b] & 1)) {
            paths[lca(a, b)].push_back({a, b, c});
        }
    }

    vector<array<int, 2>> dp(n);
    auto find_child = [&](int anc, int v) -> int {
        int cur = v;
        int prv = -1;
        while (cur != anc) {
            prv = cur;
            cur = par[cur];
        }
        return prv;
    };
    auto calc = [&](int anc, int v) -> int {
        int ans = 0;
        int cur = v;
        int prv = -1;
        while (prv != anc) {
            for (int u : adj[cur]) {
                if (u != par[cur] && u != prv) {
                    ans += dp[u][1];
                }
            }
            prv = cur;
            cur = par[cur];
        }
        return ans;
    };
    auto dfs = [&](auto&& self, int v) -> void {
        for (int u : adj[v]) {
            if (u == par[v]) continue;
            self(self, u);
        }
        for (auto [a, b, c] : paths[v]) {
            if (a == v || b == v) {
                int end = a ^ b ^ v;
                int u = find_child(v, end);
                dp[u][1] = max(dp[u][1], calc(u, end) + c);
            }
        }
        vector<array<int, 2>> items;
        for (auto [a, b, c] : paths[v]) {
            if (a == v || b == v) continue;
            int aa = find_child(v, a);
            int bb = find_child(v, b);
            int ia = find(begin(adj[v]), end(adj[v]), aa) - begin(adj[v]);
            int ib = find(begin(adj[v]), end(adj[v]), bb) - begin(adj[v]);
            assert(0 <= ia && ia < (int)adj[v].size());
            assert(0 <= ib && ib < (int)adj[v].size());
            int mask = (1 << ia) | (1 << ib);
            int inc = c + calc(aa, a) + calc(bb, b) - dp[aa][1] - dp[bb][1];
            items.push_back({mask, inc});
            // cerr << ia << " " << ib << " " << inc << "\n";
        }
        int k = adj[v].size();
        vector<int> bdp(1 << k);
        for (int u : adj[v]) {
            if (u == par[v]) continue;
            bdp[0] += dp[u][1];
        }
        for (int mask = 0; mask < (1 << k); ++mask) {
            for (auto [tmask, w] : items) {
                if ((mask | tmask) == mask) {
                    bdp[mask] = max(bdp[mask], bdp[mask ^ tmask] + w);
                }
            }
        }
        dp[v][0] = *max_element(begin(bdp), end(bdp));
        dp[v][1] = dp[v][0];
    };
    dfs(dfs, 0);

    for (int i = 0; i < n; ++i) {
        // fprintf(stderr, "dp[%d][0] = %d\tdp[%d][1] = %d\n", i+1, dp[i][0], i+1, dp[i][1]);
    }

    int ans = 0;
    for (auto [_, __, c] : e) {
        ans += c;
    }
    ans -= dp[0][0];
    
    cout << ans << "\n";
}

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