Submission #694425

#	Time	Username	Problem	Language	Result	Execution time	Memory
694425		Neos	Džumbus (COCI19_dzumbus)	C++14	110 / 110	126 ms	26936 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
typedef long long ll;
typedef pair<ll, ll> ii;

template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}

const int N = 2e3 + 7;
int n, m, q, sz[N];
ll f[N][N], g[N][N], d[N];
bool done[N];
vector<int> adj[N];

void dfs1(int u, int par) {
    done[u] = 1;
    for (int v: adj[u]) if (v != par)
        dfs1(v, u);
}

// f[u]: node u exclusive, g[u]: vice versa
void dfs2(int u, int par) {
    sz[u] = 1;
    g[u][1] = d[u];
    f[u][0] = 0;
    for (int v: adj[u]) if (v != par) {
        dfs2(v, u);
        for (int i = sz[u]; ~i; i--) {
            for (int j = sz[v]; ~j; j--) {
                minimize(f[u][i + j], f[u][i] + f[v][j]);
                if (j > 1) minimize(f[u][i + j], f[u][i] + g[v][j]);
                if (i > 1) minimize(g[u][i + j], g[u][i] + f[v][j]);

                minimize(g[u][i + j + 1], g[u][i] + f[v][j] + d[v]);
                minimize(g[u][i + j + 1], f[u][i] + g[v][j] + d[u]);
                minimize(g[u][i + j], g[u][i] + g[v][j]);
                minimize(g[u][i + j + 2], f[u][i] + f[v][j] + d[u] + d[v]);
            }
        }
        sz[u] += sz[v];
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> d[i];
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) if (!done[i]) {
        adj[i].push_back(0);
        adj[0].push_back(i);
        dfs1(i, -1);
    }

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            f[i][j] = g[i][j] = 1e18;
    dfs2(0, -1);

    cin >> q;
    for (int s; q; q--) {
        cin >> s;
        for (int k = n; k >= 0; k--) {
            if (f[0][k] <= s) {
                cout << k << '\n';
                break;
            }
        }
    }
}

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