oj.uz

Submission #694425

# Submission time Handle Problem Language Result Execution time Memory
694425 2023-02-04T05:16:48 Z Neos Džumbus (COCI19_dzumbus) C++14
110 / 110
 126 ms 26936 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24200 KB Output is correct
2 Correct 15 ms 24148 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24200 KB Output is correct
2 Correct 15 ms 24148 KB Output is correct
3 Correct 60 ms 26384 KB Output is correct
4 Correct 63 ms 26936 KB Output is correct
5 Correct 126 ms 26572 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3352 KB Output is correct
2 Correct 32 ms 3228 KB Output is correct
3 Correct 50 ms 3660 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24200 KB Output is correct
2 Correct 15 ms 24148 KB Output is correct
3 Correct 60 ms 26384 KB Output is correct
4 Correct 63 ms 26936 KB Output is correct
5 Correct 126 ms 26572 KB Output is correct
6 Correct 29 ms 3352 KB Output is correct
7 Correct 32 ms 3228 KB Output is correct
8 Correct 50 ms 3660 KB Output is correct
9 Correct 61 ms 26168 KB Output is correct
10 Correct 72 ms 26760 KB Output is correct
11 Correct 119 ms 26544 KB Output is correct