oj.uz

Submission #870840

# Submission time Handle Problem Language Result Execution time Memory
870840 2023-11-09T09:33:38 Z underwaterkillerwhale Džumbus (COCI19_dzumbus) C++17
110 / 110
 37 ms 26704 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define rep(i,m,n) for(int i=m; i<=n; i++)
#define reb(i,m,n) for(int i=m; i>=n; i--)
#define iter(id, v) for (auto id : v)
#define ii pair<int,int>
#define fs first
#define se second
#define pb push_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
#define el cout <<"\n"

template<typename A, typename B> ostream& operator<<(ostream& out, const pair<A, B> &v) { out << "(" << v.fs <<"," << v.se << ") "; return out; }

//#ifndef ONLINE_JUDGE
//    #include "debug.h"
//#else
//    #define deb(...) 23
//    #define ___
//    #define n____
//#endif

mt19937 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const ll N = 1e3 + 7;
const ll Mod = 1e9 + 7;
const ll bse = 137;
const ll szBL = 650;
const ll INF = 1e18;

int n, m, Q;
ll D[N];
vector<int> ke[N];
int subtree[N];
int dd[N];
ll dp[N][N][2], f[N][N][2];

int nn;
ll pre[N];

ii qr[N];

inline void minimize(ll &a, ll b) { if (a > b) a = b; }

void dfs (int u, int pa) {
    vector<int> Ch = {0};
    subtree[u] = 1, dd[u] = 1;
    iter (&v, ke[u]) {
        if (v != pa) {
            dfs(v, u);
            subtree[u] += subtree[v];
            Ch.pb(v);
        }
    }
    int nC = SZ(Ch) - 1;
    rep (i, 0, nC)
    rep (j, 0, subtree[u]) {
        f[i][j][0] = f[i][j][1] = INF;
    }
    int tot = 1;
    f[0][0][0] = 0;
    f[0][0][1] = D[u];
    rep (i, 1, nC) {
        int &curC = Ch[i];
        rep (k, 0, tot)
        rep (t, 0, subtree[curC]) {
            minimize(f[i][k + t][0], f[i - 1][k][0] + min(dp[curC][t][1], dp[curC][t][0]));
            if (k) {
                minimize(f[i][k + t][1], f[i - 1][k - 1][0] + dp[curC][t][1] + D[u]);
                if (t) {
                    minimize(f[i][k + t][1], f[i - 1][k - 1][0] + dp[curC][t - 1][0] + D[curC] + D[u]);
                }
            }
            f[i][k + t][1] = min({f[i][k + t][1],
                                 f[i - 1][k][1] + dp[curC][t][1],
                                 f[i - 1][k][1] + dp[curC][t][0]});
            if (t) {
                minimize(f[i][k + t][1], f[i - 1][k][1] + dp[curC][t - 1][0] + D[curC]);
            }
        }
        tot += subtree[curC];
    }
    rep (k, 0, subtree[u]) {
        dp[u][k][0] = f[nC][k][0];
        dp[u][k][1] = f[nC][k][1];
    }
}

void chloe_solution() {
    cin >> n >> m;
    D[0] = INF;
    rep (i, 1, n) cin >> D[i];
    rep (i, 1, m) {
        ll u, v;
        cin >> u >> v;
        ke[u].pb(v);
        ke[v].pb(u);
    }
    rep (i, 1, n) {
        if (dd[i] == 0) {
            dfs(i, 0);
            ke[0].pb(i);
            ke[i].pb(0);
        }
    }
    dfs(0, 0);
    reb (i, n, 0) {
        minimize(dp[0][i][0], dp[0][i + 1][0]);
    }
    cin >> Q;
    rep (qi, 1, Q) {
        cin >> qr[qi].fs;
        qr[qi].se = qi;
    }
    sort (qr + 1, qr + 1 + Q);
    vector<int> ans(Q + 2);
    ll cur = 0;
    rep (qi, 1, Q) {
        while (cur <= n && dp[0][cur][0] <= qr[qi].fs) ++cur;
        ans[qr[qi].se] = cur - 1;
    }
    rep (i, 1, Q) cout << ans[i] <<"\n";
}

int main() {
//     file("c");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        chloe_solution();
}
/*
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17496 KB Output is correct
2 Correct 9 ms 17500 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17496 KB Output is correct
2 Correct 9 ms 17500 KB Output is correct
3 Correct 33 ms 22668 KB Output is correct
4 Correct 36 ms 23132 KB Output is correct
5 Correct 37 ms 22856 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 9552 KB Output is correct
2 Correct 30 ms 9340 KB Output is correct
3 Correct 28 ms 9744 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17496 KB Output is correct
2 Correct 9 ms 17500 KB Output is correct
3 Correct 33 ms 22668 KB Output is correct
4 Correct 36 ms 23132 KB Output is correct
5 Correct 37 ms 22856 KB Output is correct
6 Correct 25 ms 9552 KB Output is correct
7 Correct 30 ms 9340 KB Output is correct
8 Correct 28 ms 9744 KB Output is correct
9 Correct 29 ms 22192 KB Output is correct
10 Correct 33 ms 24920 KB Output is correct
11 Correct 32 ms 26704 KB Output is correct