oj.uz

답안 #699183

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
699183 2023-02-16T00:51:04 Z badont Džumbus (COCI19_dzumbus) C++17
110 / 110
 50 ms 11444 KB 
#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
#define all(x) x.begin(),x.end()
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);

    ll q; cin >> q;
    vector<ll> rets;
    for (int i = 2; i <= n; i++)
        rets.pb(i);

    sort(all(rets), [&](ll x, ll y){
        return dp[0][0][x] < dp[0][0][y];
    });

    vector<ll> p = rets;
    for (int i = 1; i < (int)p.size(); i++) {
        p[i] = max(p[i], p[i - 1]);
    }

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

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

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from dzumbus.cpp:4:
dzumbus.cpp: In function 'void solve()':
dzumbus.cpp:181: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]
  181 |         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:162:19:   required from here
dzumbus.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) "zzz"
      |                    ^~~~~
dzumbus.cpp:129:13: note: in expansion of macro 'debug'
  129 |             debug(u, g, "here");
      |             ^~~~~
dzumbus.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) "zzz"
      |                    ^~~~~
dzumbus.cpp:159:9: note: in expansion of macro 'debug'
  159 |         debug(g, dp0, dp1);
      |         ^~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 8532 KB Output is correct
2 Correct 17 ms 8588 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 8532 KB Output is correct
2 Correct 17 ms 8588 KB Output is correct
3 Correct 45 ms 10700 KB Output is correct
4 Correct 48 ms 11444 KB Output is correct
5 Correct 50 ms 10976 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 1168 KB Output is correct
2 Correct 29 ms 920 KB Output is correct
3 Correct 34 ms 2704 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 8532 KB Output is correct
2 Correct 17 ms 8588 KB Output is correct
3 Correct 45 ms 10700 KB Output is correct
4 Correct 48 ms 11444 KB Output is correct
5 Correct 50 ms 10976 KB Output is correct
6 Correct 29 ms 1168 KB Output is correct
7 Correct 29 ms 920 KB Output is correct
8 Correct 34 ms 2704 KB Output is correct
9 Correct 39 ms 2772 KB Output is correct
10 Correct 40 ms 3300 KB Output is correct
11 Correct 41 ms 3072 KB Output is correct