Submission #707739

#	Time	Username	Problem	Language	Result	Execution time	Memory
707739		badont	Training (IOI07_training)	C++17	0 / 100	6 ms	980 KiB

training

#include<iostream>
#include<random>
#include<chrono>
#include<vector>
#include<algorithm>
#include<queue>
#include<array>
#include<cassert>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

#define pb push_back
#define all(x) x.begin(),x.end()

void solve() {
    ll n, m;
    cin >> n >> m;

    vector<array<ll, 3>> agg;
    vector e(n, vector<ll>());
    ll ans = 0;
    while (m--) {
        ll x, y, c;
        cin >> x >> y >> c;
        x--; y--;

        if (c == 0) {
            e[x].pb(y);
            e[y].pb(x);
        } else {
            agg.push_back({x, y, c});
            ans += c;
        }
    }

    vector bl(n, vector<ll>(20, -1));
    vector<ll> depth(n);
    vector children(n, vector<ll>());
    vector<ll> tin(n), tout(n);
    ll cc = 0;
    auto dfs = [&](auto dfs, ll g, ll p, ll d) -> void {
        bl[g][0] = p;
        tin[g] = cc++;
        for (int i = 1; i < 20; i++) if (bl[g][i - 1] != -1)
            bl[g][i] = bl[bl[g][i - 1]][i - 1];
        
        depth[g] = d;

        for (auto u : e[g]) if (u != p) {
            dfs(dfs, u, g, d + 1);
            children[g].pb(u);
        }
        tout[g] = cc++;
    };
    dfs(dfs, 0, -1, 1);

    #ifdef LOCAL
    cout << "DEPTHS: ";
    for (auto u : depth) cout << u << ' ';
    cout << '\n';
    #endif

    auto ancestor = [&](ll x, ll y) -> bool {
        if (x == -1) return true;
        return tin[x] <= tin[y] and tout[x] >= tout[y];
    };


    auto lca = [&](ll x, ll y) -> ll {
        ll ox = x, oy = y;
        assert(x != -1 and y != -1);
        if (depth[x] <= depth[y]) swap(x, y);
        assert(depth[x] >= depth[y]);
        
        for (int i = 19; i >= 0; i--) {
            if (bl[x][i] == -1 or depth[bl[x][i]] < depth[y]) continue;
            x = bl[x][i];
        }
        if (x == y) return x;
        for (int i = 19; i >= 0; i--) {
            if (bl[x][i] == bl[y][i]) continue;
            x = bl[x][i], y = bl[y][i];
        }
        assert(bl[x][0] != -1);
        ll ret = bl[x][0];
        assert(ancestor(ret, ox) and ancestor(ret, oy));
        return ret;    
    };

    for (int i = 0; i < n; i++)
        sort(all(children[i]));

    auto get_idx = [&](ll g, ll c) -> ll {
        auto iter = lower_bound(all(children[g]), c);
        assert(iter != children[g].end() and *iter == c);
        return iter - children[g].begin();
    };

    auto get_ricky = [&](ll root, ll g) -> ll {
        assert(ancestor(root, g));
        #ifdef LOCAL
        cout << "RICKY: " << root << " " << g << " ";
        #endif
        for (int i = 19; i >=0; i--) {
            if (ancestor(bl[g][i], root)) continue;
            g = bl[g][i];
        }
        #ifdef LOCAL
        cout << g << '\n';
        #endif
        return g;
    };

    vector look(n, vector<array<ll, 3>>());
    vector<ll> dp(n);

    for (auto [x, y, c] : agg) {
        if (depth[x] % 2 != depth[y] % 2) {
            continue;
        }
        look[lca(x, y)].pb({x, y, c});
        #ifdef LOCAL
        #endif
    }

    vector dp_st(n, vector<ll>());
    

    auto dfs_2 = [&](auto dfs_2, ll g, ll p) -> ll {
        for (auto u : children[g]) dfs_2(dfs_2, u, g);

        ll m = (int)children[g].size();
        #ifdef LOCAL
        #endif
        auto& dp_here = dp_st[g];
        dp_here.resize(1 << m);
        for (int i = 0; i < m; i++) {
            ll u = children[g][i];
            dp_here[1 << i] = dp[u];
        }

        for (auto [x, y, c] : look[g]) {
            assert(!(x == g and y == g));
            if (x == g) swap(x, y);
            if (y == g) {
                ll rx = get_ricky(g, x);
                auto idx = get_idx(g, rx); 
                ll m2 = (1 << ((int)children[rx].size())) - 1;
                if (x != rx) m2 -= (1 << get_idx(rx, get_ricky(rx, x)));
                assert(idx < m); 
                dp_here[1 << idx] = max(dp_here[1 << idx], dp_st[rx][m2] + c);
                continue;
            }
            ll xr = get_ricky(g, x);
            ll yr = get_ricky(g, y);
            assert(xr != yr);
            ll xid = get_idx(g, xr);
            ll yid = get_idx(g, yr);
            assert(xid != yid);
            assert(xid < m and yid < m);
            ll b = (1 << yid) | (1 << xid);
            #ifdef LOCAL
            cout << "Extra edge at: " << g << " abt " << x << ' ' << y << ' ' << "with ids: " << xid << ' ' << yid << " and val: " << c << '\n';
            #endif
            ll bmx = (1 << ((int)children[xr].size())) - 1;
            ll bmy = (1 << ((int)children[yr].size())) - 1;
            if (x != xr) bmx -= (1 << get_idx(xr, get_ricky(xr, x)));
            if (y != yr) bmy -= (1 << get_idx(yr, get_ricky(yr, y)));
            dp_here[b] = max(dp_here[b], dp_st[xr][bmx] + dp_st[yr][bmy] + c);
        } 

        for (int mask = 0; mask < (1 << m); mask++) {
            for (int i = 0; i < m; i++) if ((mask >> i) & 1) {
                dp_here[mask] = max(dp_here[mask], dp_here[mask ^ (1 << i)] + dp_here[1 << i]);
            }
            for (int i = 0; i < m; i++) if ((mask >> i) & 1) {
                for (int j = i + 1; j < m; j++) if ((mask >> j) & 1) {
                    int b = (1 << i) | (1 << j);
                    #ifdef LOCAL
                    cout << "UPDATING DP... ";
                    cout << dp_here[mask] << ' ' << dp_here[mask ^ b] + dp_here[b] << '\n';
                    #endif
                    dp_here[mask] = max(dp_here[mask], dp_here[mask ^ b] + dp_here[b]);
                }
            }
        }

        dp[g] = dp_here[(1 << m) - 1];
        return dp[g];
    };

    ll sub = dfs_2(dfs_2, 0, -1);
    #ifdef LOCAL
    cout << ans << ' ' << sub << '\n';
    #endif
    ans -= sub;

    cout << ans << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll t = 1;
    while(t--)
        solve();
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 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