oj.uz

Submission #1091798

# Submission time Handle Problem Language Result Execution time Memory
1091798 2024-09-22T07:20:02 Z anhthi Džumbus (COCI19_dzumbus) C++14
110 / 110
 156 ms 66384 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define sz(v) ((int) (v).size())
#define mp(x, y) make_pair(x, y)
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define ctz __builtin_ctzll
#define clz __builtin_clzll
#define popcount __builtin_popcountll
#define lg(x) (63 - clz(x))

template <class X, class Y>
    inline bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        return false;
    }
template <class X, class Y>
    inline bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        return false;
    }
template <class X>
    inline void compress(vector<X> &a) {
        sort(all(a));
        a.resize(unique(all(a)) - a.begin());
    }

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

ll rand(ll l, ll r) {
    return l + abs((ll) rng()) % (r - l + 1);
}

const ll oo = (ll) 1e18;
const int inf = (int) 1e9 + 7, mod = (int) 1e9 + 7;

void add(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}

const int mxn = (int) 2e3 + 5, lg = (int) 14;
int n, m, q;
ll a[mxn];

vector<int> g[mxn];

namespace one {
    bool one() {
        return true;
    }

    int childs[mxn];
    ll f[mxn][mxn][2], dp[mxn][2];

    bool mark[mxn];

    void dfsMark(int u, int p) {
        mark[u] = true;
        for (int v : g[u]) if (v != p) {
            dfsMark(v, u);
        }
        return;
    }

    void dfs(int u, int p) {
        childs[u] = 1;
        for (int v : g[u]) if (v != p) {
            dfs(v, u);
            childs[u] += childs[v];
        }

        int siz = 0;

        /*
            f[u][k][flag]:
                in subtree u we satisify k guys and check whenever the
                u'th guys is connected to its childs
        */
        f[u][0][0] = 0;
        for (int v : g[u]) if (v != p) {
            for (int i = 0; i <= siz+childs[v]+2; ++i)
                memset(dp[i], 32, sizeof dp[i]);
            for (int i = 0; i <= siz; ++i)
            for (int j = 0; j <= childs[v]; ++j) {
                minimize(dp[i+j][0], f[u][i][0] + min(f[v][j][0], f[v][j][1]));
                if (i) {
                    minimize(dp[i+j][1], f[u][i][1] + f[v][j][0]);
                    minimize(dp[i+j][1], f[u][i][1] + f[v][j][1]);
                    minimize(dp[i+j+1][1], f[u][i][1] + f[v][j][0] + a[v]);

//                    minimize(dp[i+j][1], f[u][i][1] + min(f[v][j][0], f[v][j][1]));
//                    minimize(dp[i+j][1], f[u][i][1] + min(f[v][j][0] + a[v], f[v][j][1]));
                }
                minimize(dp[i+j+1][1], f[u][i][0] + a[u] + f[v][j][1]);
                minimize(dp[i+j+2][1], f[u][i][0] + a[u] + a[v] + f[v][j][0]);
//                minimize(dp[i+j+1][1], f[u][i][0] + a[u] + min( f[v][j][0] + a[v], f[v][j][1] ));
            }
            siz = siz + childs[v] + 2;
            for (int i = 0; i <= siz; ++i) {
                f[u][i][0] = dp[i][0]; f[u][i][1] = dp[i][1];
            }
        }

//        printf("PHASE OPEN FOR: %d\n", u);
//        cout << "PHASE: " << u << "\n";
//        for (int i = 0; i <= childs[u]; ++i) {
//            cout << i << ' ' << f[u][i][0] << ' ' << f[u][i][1] << '\n';
//            printf("f[%llu][%llu][%llu] = %llu and f[%llu][%llu][%llu] = %llu\n",
//                   u, i, 0, f[u][i][0], u, i, 1, f[u][i][1]);
//        }
//        cout << "END PHASE:\n\n";
//        printf("END PHASE:\n\n");

    }

    void solve() {

        memset(f, 32, sizeof f);

//        cout << f[0][0][0] << '\n';
//        cout << f[0][0][0] +f[0][0][0]  << '\n';
//        cout << f[0][0][0] +f[0][0][0] + f[0][0][0] << '\n';

        a[0] = oo;
        for (int i = 1; i <= n; ++i) if (!mark[i]) {
            dfsMark(i, 0);
            g[0].push_back(i);
//            g[i].push_back(0);
        }

        dfs(0, -1);

        cin >> q;
        for (int i = 1; i <= q; ++i) {
            int val; cin >> val;

            int ans = 0;
            for (int j = n; j >= 1; --j) {
                if (min(f[0][j][0], f[0][j][1]) <= val) {
                    maximize(ans, j); break;
                }
            }

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

        return;
    }
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    {
        if (one::one()) return one::solve(), 0;
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 63568 KB Output is correct
2 Correct 29 ms 63372 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 63568 KB Output is correct
2 Correct 29 ms 63372 KB Output is correct
3 Correct 71 ms 65688 KB Output is correct
4 Correct 71 ms 66384 KB Output is correct
5 Correct 156 ms 65868 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 65360 KB Output is correct
2 Correct 45 ms 65124 KB Output is correct
3 Correct 58 ms 65616 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 63568 KB Output is correct
2 Correct 29 ms 63372 KB Output is correct
3 Correct 71 ms 65688 KB Output is correct
4 Correct 71 ms 66384 KB Output is correct
5 Correct 156 ms 65868 KB Output is correct
6 Correct 44 ms 65360 KB Output is correct
7 Correct 45 ms 65124 KB Output is correct
8 Correct 58 ms 65616 KB Output is correct
9 Correct 67 ms 65360 KB Output is correct
10 Correct 74 ms 66128 KB Output is correct
11 Correct 154 ms 65824 KB Output is correct