Submission #699182

#	Time	Username	Problem	Language	Result	Execution time	Memory
699182		badont	Džumbus (COCI19_dzumbus)	C++17	0 / 110	19 ms	17236 KiB

dzumbus

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;

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 T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
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<T, string>::value,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 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

#define FOR(i,n) for (int i = 1; i <= n; i++)
#define F0R(i,n) for (int i = 0; i < n; i++)
#define pb push_back
#define f first
#define s second
using ll = long long;
using ld = long double;


struct DSU {
	ll mxn;
	vector<ll> par, sz;

	DSU(ll ini){
		mxn = ini;
		par.assign(ini + 5, 0);
		sz.assign(ini + 5, 1);
		FOR(i, mxn) par[i] = i;
	}

	ll fnd(ll g){
		if(g == par[g]) return g;
 		return par[g] = fnd(par[g]);
	}

	void uni(ll a, ll b){
		a = fnd(a), b = fnd(b);
		if(a == b) return;

		if(sz[a] <= sz[b]) swap(a, b); // a bigger
		par[b] = a; sz[a] += sz[b];
	}
};

const ll INF = 1e18;

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

    n++;
    vector<ll> D(n);
    D[0] = INF;
    FOR (i, n - 1) cin >> D[i];
    vector e(n, vector<ll>());
    DSU dsu(n - 1);
    while (m--) {
        ll x, y;
        cin >> x >> y;
        dsu.uni(x, y);
        e[x].pb(y);
        e[y].pb(x);
    }

    vector<ll> vis(n);
    FOR (i, n - 1) if (!vis[dsu.fnd(i)]) {
        vis[dsu.fnd(i)] = true;
        e[0].pb(dsu.fnd(i));
        e[dsu.fnd(i)].pb(0);
    }

    vector dp(2, vector(n, vector<ll>()));
    vector<ll> sub(n);
    auto dfs = [&](auto dfs, ll g, ll p) -> void {
        sub[g] = 1;
        for (auto u : e[g]) if (u != p) {
            dfs(dfs, u, g);
            sub[g] += sub[u];
        }

        auto& dp0 = dp[0][g], &dp1 = dp[1][g];
        dp0.resize(2);
        dp1.resize(2);
        //dp0 force non inclusion
        //dp1 force inclusion
        dp0[0] = 0; dp1[0] = INF;
        dp0[1] = INF; dp1[1] = INF;

        ll c_size = 1;
        for (auto& u : e[g]) if (u != p) {
            auto& cp0 = dp[0][u];
            auto& cp1 = dp[1][u];

            c_size += sub[u];
            //debug(c_size);
            vector<ll> ndp0(c_size + 1, INF), ndp1(c_size + 1, INF);
            
            for (int i = 0; i < (int)dp0.size(); i++) {
                for (int j = 0; j < (int)cp0.size(); j++) if (dp0[i] < INF and cp0[j] < INF) {
                    assert(i + j < (int)ndp0.size());
                    ndp0[i + j] = min(ndp0[i + j], dp0[i] + cp0[j]);
                }
                for (int j = 0; j < (int)cp1.size(); j++) if (dp0[i] < INF and cp1[j] < INF) {
                    //debug(u, g, i, j, dp0[i], cp1[j]);
                    assert(i + j < (int)ndp0.size());
                    ndp0[i + j] = min(ndp0[i + j], dp0[i] + cp1[j]);
                }
            }

            debug(u, g, "here");

            for (int i = 0; i < (int)dp0.size(); i++) {
                for (int j = 0; j < (int)cp0.size(); j++) if (dp0[i] < INF and cp0[j] < INF and D[g] < INF and D[u] < INF){
                    assert(i + j + 2 < (int)ndp1.size()); 
                    ndp1[i + j + 2] = min(ndp1[i + j + 2], dp0[i] + cp0[j] + D[g] + D[u]);
                }
                for (int j = 0; j < (int)cp1.size(); j++) if (dp0[i] < INF and cp1[j] < INF and D[g] < INF){
                    ndp1[i + j + 1] = min(ndp1[i + j + 1], dp0[i] + cp1[j] + D[g]);
                }
            }

            for (int i = 0; i < (int)dp1.size(); i++) {
                for (int j = 0; j < (int)cp0.size(); j++) if (dp1[i] != INF and cp0[j] != INF) {
                    assert(i + j + 1 < (int)ndp1.size());
                    ndp1[i + j] = min(ndp1[i + j], dp1[i] + cp0[j]);
                    if (D[u] < INF) ndp1[i + j + 1] = min(ndp1[i + j + 1], dp1[i] + cp0[j] + D[u]);
                }
                for (int j = 0; j < (int)cp1.size(); j++) if (dp1[i] != INF and cp1[j] != INF) {
                    assert(i + j < (int)ndp1.size());
                    ndp1[i + j] = min(ndp1[i + j], dp1[i] + cp1[j]);
                }
            }

            swap(ndp0, dp0);
            swap(ndp1, dp1);
            ndp0.clear();
            ndp1.clear();
        }

        debug(g, dp0, dp1);
    };

    dfs(dfs, 0, -1);

    for (int i = 3; i <= n; i++) {
        assert(dp[0][i] > dp[0][i - 1]);
    }

    ll q; cin >> q;
    while (q--) {
        ll x; cin >> x;
        auto& ref = dp[0][0];
        assert(ref[0] == 0 and ref.size() == n + 1);
        ll lo = 2, hi = n, mid;
        while (lo < hi) {
            mid = (lo + hi + 1) >> 1;
            if (ref[mid] <= x) lo = mid;
            else hi = mid - 1;
        }
        cout << (lo < (int)ref.size() and ref[lo] <= x ? lo : 0) << '\n';
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    solve();
    return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from dzumbus.cpp:4:
dzumbus.cpp: In function 'void solve()':
dzumbus.cpp:171:43: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  171 |         assert(ref[0] == 0 and ref.size() == n + 1);
      |                                ~~~~~~~~~~~^~~~~~~~
dzumbus.cpp: In instantiation of 'solve()::<lambda(auto:1, ll, ll)> [with auto:1 = solve()::<lambda(auto:1, ll, ll)>; ll = long long int]':
dzumbus.cpp:161:19:   required from here
dzumbus.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) "zzz"
      |                    ^~~~~
dzumbus.cpp:128:13: note: in expansion of macro 'debug'
  128 |             debug(u, g, "here");
      |             ^~~~~
dzumbus.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) "zzz"
      |                    ^~~~~
dzumbus.cpp:158:9: note: in expansion of macro 'debug'
  158 |         debug(g, dp0, dp1);
      |         ^~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30