Submission #1279106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279106		traktor74	Džumbus (COCI19_dzumbus)	C++20	110 / 110	38 ms	13200 KiB

dzumbus

#include<bits/stdc++.h>

using namespace std;

int const maxn = 1e3 + 5;
int a[maxn], used[maxn], inf = 1e9 + 7;
vector < int > g[maxn];
int dp[maxn][maxn][3];
int b[maxn], sz[maxn];
int f[maxn][3];

void calc(int v) {
    used[v] = 1;
    for (auto u : g[v]) {
        if (!used[u]) calc(u);
    }
}

void dfs(int v, int p) {
    for (int i = 0; i < maxn; i++) {
        dp[v][i][0] = dp[v][i][1] = dp[v][i][2] = inf;
    }
    dp[v][0][0] = 0;
    dp[v][0][1] = a[v];
    sz[v] = 1;
    for (auto u : g[v]) {
        if (u == p) continue;
        dfs(u, v);
        for (int i = 0; i <= sz[v] + sz[u]; i++) {
            f[i][0] = f[i][1] = f[i][2] = inf;
        }
        for (int i = 0; i <= sz[v]; i++) {
            for (int j = 0; j < 3; j++) {
                for (int z = 0; z <= sz[u]; z++) {
                    for (int d = 0; d < 3; d++) {
                        int nxt_i = i + z;
                        int nxt_j = j;
                        if (j == 1) {
                            if (d == 1) {
                                nxt_j = 2;
                                nxt_i += 2;
                            } else if (d == 2) {
                                nxt_j = 2;
                                nxt_i++;
                            }
                        } else if (j == 2) {
                            if (d == 1) {
                                nxt_i++;
                            }
                        }
                        f[nxt_i][nxt_j] = min(f[nxt_i][nxt_j], dp[v][i][j] + dp[u][z][d]);
                    }
                }
            }
        }
        sz[v] += sz[u];
        for (int i = 0; i <= sz[v]; i++) {
            dp[v][i][0] = f[i][0];
            dp[v][i][1] = f[i][1];
            dp[v][i][2] = f[i][2];
        }
    }
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    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);
    }
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            g[0].push_back(i);
            calc(i);
        }
    }
    a[0] = inf;
    dfs(0, -1);
    for (int i = 1; i <= n; i++) {
        b[i] = dp[0][i][0];
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int x;
        cin >> x;
        int ans = upper_bound(b + 1, b + n + 1, x) - b - 1;
        cout << ans << '\n';
    }
    return 0;
}

Compilation message (stderr)

dzumbus.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 | main() {
      | ^~~~

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