oj.uz

Submission #1119166

# Submission time Handle Problem Language Result Execution time Memory
1119166 2024-11-26T16:49:42 Z LonlyR Džumbus (COCI19_dzumbus) C++17
110 / 110
 390 ms 34996 KB 
#include<bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 1e3 + 5;
int n, m, q;
int val[maxn], vis[maxn], take[maxn], sz[maxn], state[maxn];
int dp[maxn][2][maxn][2];
vector<int> adj[maxn];

inline void MIN(int &x, int y)
{
    x = min(x, y);
}

void dfs(int x, int p)
{
    vis[x] = 1;
    sz[x] = (x > 0 ? 1 : n);
    for (int i : adj[x]) if (!vis[i])
        dfs(i, x),
        sz[x] += sz[i];
    memset(dp[x], 0x3f, sizeof dp[x]);
    dp[x][0][0][0] = 0;
    int be = 0, cu = 1;
    for (int u : adj[x]) if (u != p)
    {
        memset(dp[x][cu], 0x3f, sizeof dp[x][cu]);
        int st = state[u];
        for (int i = 0; i <= sz[x]; i++)
            for (int j = 0; j <= sz[u]; j++)
            {
                if (j > i) break;
                MIN(dp[x][cu][i][0], min(dp[u][st][j][0], dp[u][st][j][1]) + dp[x][be][i - j][0]);
                MIN(dp[x][cu][i][1], min(dp[u][st][j][0], dp[u][st][j][1]) + dp[x][be][i - j][1]);
                if (j) MIN(dp[x][cu][i][1], dp[u][st][j - 1][0] + dp[x][be][i - j][1] + val[u]);
                if (x && i - j) MIN(dp[x][cu][i][1], dp[u][st][j][1] + dp[x][be][i - j - 1][0] + val[x]);
                if (x && j && i - j) MIN(dp[x][cu][i][1], dp[u][st][j - 1][0] + dp[x][be][i - j - 1][0] + val[x] + val[u]);
            }
        swap(be, cu);
    }
    state[x] = be;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> val[i];
    for (int i = 1, u, v; i <= m; i++)
        cin >> u >> v,
        adj[u].emplace_back(v),
        adj[v].emplace_back(u);
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs(i, i),
            adj[0].emplace_back(i);
    dfs(0, 0);
    take[n + 1] = 1e18;
    for (int i = n; i >= 2; i--)
    {
        int st = state[0];
        take[i] = min({take[i + 1], dp[0][st][i][0], dp[0][st][i][1]});
    }
    cin >> q;
    while (q--)
    {
        int x; cin >> x;
        int ans = upper_bound(take + 2, take + n + 1, x) - take - 1;
        cout << (ans <= 1 ? 0 : ans) << "\n";
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 32076 KB Output is correct
2 Correct 306 ms 32116 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 32076 KB Output is correct
2 Correct 306 ms 32116 KB Output is correct
3 Correct 390 ms 34320 KB Output is correct
4 Correct 223 ms 34996 KB Output is correct
5 Correct 194 ms 34432 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6740 KB Output is correct
2 Correct 32 ms 6652 KB Output is correct
3 Correct 30 ms 6996 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 32076 KB Output is correct
2 Correct 306 ms 32116 KB Output is correct
3 Correct 390 ms 34320 KB Output is correct
4 Correct 223 ms 34996 KB Output is correct
5 Correct 194 ms 34432 KB Output is correct
6 Correct 25 ms 6740 KB Output is correct
7 Correct 32 ms 6652 KB Output is correct
8 Correct 30 ms 6996 KB Output is correct
9 Correct 43 ms 34120 KB Output is correct
10 Correct 45 ms 34636 KB Output is correct
11 Correct 36 ms 34380 KB Output is correct