oj.uz

Submission #925829

# Submission time Handle Problem Language Result Execution time Memory
925829 2024-02-12T09:36:30 Z a_l_i_r_e_z_a Džumbus (COCI19_dzumbus) C++17
110 / 110
 169 ms 25144 KB 
// In the name of God
// Hope is last to die

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
// #define int long long    
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())

const int maxn = 1000 + 5;
const ll inf = 1e15 + 7;
ll n, m, dp[maxn][maxn][3], a[maxn], cnt[maxn], tmp[maxn][3];
bool mark[maxn];
vector<int> adj[maxn];

void fake(int v, int p){
    mark[v] = 1;
    for(auto u: adj[v]) if(!mark[u]) fake(u, v);
}

void dfs(int v, int p){
    dp[v][1][1] = a[v];
    dp[v][0][0] = 0;
    cnt[v] = 1;
    for(auto u: adj[v]){
        if(u == p) continue;
        dfs(u, v);
        for(int i = 0; i <= cnt[u] + cnt[v]; i++) for(int j = 0; j < 3; j++) tmp[i][j] = inf;
        for(int i = 0; i < cnt[v]; i++){
            for(int j = 0; j <= cnt[u]; j++){
                smin(tmp[i + j][0], dp[v][i][0] + min(dp[u][j][2], dp[u][j][0]));
            }
        }
        for(int i = 1; i <= cnt[v]; i++){
            for(int j = 0; j <= cnt[u]; j++){
                smin(tmp[i + j][1], dp[v][i][1] + dp[u][j][0]);
            }
        }
        for(int i = 1; i <= cnt[v]; i++){
            for(int j = 0; j <= cnt[u]; j++){
                smin(tmp[i + j][2], dp[v][i][1] + min(dp[u][j][1], dp[u][j][2]));
                smin(tmp[i + j][2], dp[v][i][2] + min(dp[u][j][0], min(dp[u][j][1], dp[u][j][2])));
            }
        }
        cnt[v] += cnt[u];
        for(int i = 0; i <= cnt[v]; i++){
            for(int j = 0; j < 3; j++) dp[v][i][j] = tmp[i][j];
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) for(int k = 0; k < 3; k++) dp[i][j][k] = inf;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        u--, v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for(int i = 0; i < n; i++){
        if(!mark[i]){
            fake(i, -1);
            adj[n].pb(i);
        }
    }
    dfs(n, -1);
    int q; cin >> q;
    while(q--){
        int s; cin >> s;
        int ans = 0;
        for(int i = 2; i <= n; i++) if(dp[n][i][0] <= s) ans = i;
        cout << ans << '\n';
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 24152 KB Output is correct
2 Correct 8 ms 24408 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 24152 KB Output is correct
2 Correct 8 ms 24408 KB Output is correct
3 Correct 160 ms 25144 KB Output is correct
4 Correct 169 ms 25028 KB Output is correct
5 Correct 164 ms 25056 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5204 KB Output is correct
2 Correct 39 ms 5200 KB Output is correct
3 Correct 42 ms 4840 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 24152 KB Output is correct
2 Correct 8 ms 24408 KB Output is correct
3 Correct 160 ms 25144 KB Output is correct
4 Correct 169 ms 25028 KB Output is correct
5 Correct 164 ms 25056 KB Output is correct
6 Correct 40 ms 5204 KB Output is correct
7 Correct 39 ms 5200 KB Output is correct
8 Correct 42 ms 4840 KB Output is correct
9 Correct 161 ms 24748 KB Output is correct
10 Correct 162 ms 24916 KB Output is correct
11 Correct 166 ms 24656 KB Output is correct