Submission #707767

#	Time	Username	Problem	Language	Result	Execution time	Memory
707767		badont	Training (IOI07_training)	C++17	100 / 100	11 ms	1108 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 dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same_v<T, string>,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

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;
        }
    }

    constexpr ll b_lim = 10;

    vector bl(n, vector<ll>(b_lim, -1));
    vector<ll> depth(n);
    vector children(n, vector<ll>());
    vector<ll> tin(n), tout(n);
    vector<ll> par(n);
    ll cc = 0;
    auto dfs = [&](auto dfs, ll g, ll p, ll d) -> void {
        bl[g][0] = p;
        par[g] = p;
        tin[g] = cc++;
        for (int i = 1; i < b_lim; 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);

    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 = b_lim - 1; 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 = b_lim - 1; 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));
        for (int i = b_lim - 1; i >=0; i--) {
            if (ancestor(bl[g][i], root)) continue;
            g = bl[g][i];
        }
        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});
    }

    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();
        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);
            ll dp_add = 0;
            auto start_from_x = [&](ll x) {
            	ll cx = x;
            	while (par[cx] != g) {
            		ll rel_idx = get_idx(par[cx], cx);
            		ll par_sz = (int)children[par[cx]].size();
            		ll par_mask = (1 << par_sz) - (1 << rel_idx) - 1;
            		dp_add += dp_st[par[cx]][par_mask];
            		cx = par[cx];
            	}
            };
            if (y == g) {
            	dp_add += dp[x];
            	start_from_x(x);
                ll rx = get_ricky(g, x);
                auto idx = get_idx(g, rx); 
                dp_here[1 << idx] = max(dp_here[1 << idx], 
                					dp_add + c);
                continue;
            }
            dp_add += dp[x] + dp[y];
            start_from_x(x);
            start_from_x(y);
            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);
	           dp_here[b] = max(dp_here[b], dp_add + 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) {
                	debug(g,mask,i,j);
                    int b = (1 << i) | (1 << j);
                    dp_here[mask] = max(dp_here[mask], dp_here[mask ^ b] + dp_here[b]);
                }
            }
        }

        assert(dp_here[(1 << m) - 1] == *max_element(all(dp_here))); 

        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;
}

Compilation message (stderr)

training.cpp: In instantiation of 'solve()::<lambda(auto:2, ll, ll)> [with auto:2 = solve()::<lambda(auto:2, ll, ll)>; ll = long long int]':
training.cpp:207:32:   required from here
training.cpp:22:20: warning: statement has no effect [-Wunused-value]
   22 | #define debug(...) "zzz"
      |                    ^~~~~
training.cpp:194:18: note: in expansion of macro 'debug'
  194 |                  debug(g,mask,i,j);
      |                  ^~~~~

• 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