oj.uz

Submission #1023042

# Submission time Handle Problem Language Result Execution time Memory
1023042 2024-07-14T08:56:31 Z anarch_y Džumbus (COCI19_dzumbus) C++17
110 / 110
 46 ms 17748 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#define int long long

vector<int> combine(vector<int> a, vector<int> b){
    vector<int> c(sz(a)+sz(b)-1, 1e16);
    for(int i=0; i<sz(a); i++){
        for(int j=0; j<sz(b); j++){
            c[i+j] = min(c[i+j], a[i]+b[j]);
        }
    }
    return c;
}

vector<int> find_min(vector<int> a, vector<int> b){
    vector<int> c(sz(a));
    for(int i=0; i<sz(a); i++){
        c[i] = min(a[i], b[i]);
    }
    return c;
}

const int maxn = 1001;
vector<int> adj[maxn];
vector<int> dp[maxn][4];
int vis[maxn], D[maxn];

void dfs(int s, int p){
    vis[s] = 1;
    dp[s][0] = {0, (int)1e16};
    dp[s][1] = {(int)1e16, (int)1e16};
    dp[s][2] = {(int)1e16, D[s]};
    for(auto u: adj[s]){
        if(u == p) continue;
        dfs(u, s);
        dp[s][0] = combine(dp[s][0], dp[u][3]);
        vector<int> a[5];
        a[0] = combine(dp[s][1], dp[u][0]);
        a[1] = combine(dp[s][1], dp[u][1]);
        a[2] = combine(dp[s][1], dp[u][2]);
        a[3] = combine(dp[s][2], dp[u][1]);
        a[4] = combine(dp[s][2], dp[u][2]);
        dp[s][1] = a[0];
        for(int i=1; i<5; i++){
            dp[s][1] = find_min(dp[s][1], a[i]);
        }
        dp[s][2] = combine(dp[s][2], dp[u][0]);
    }
    dp[s][3] = dp[s][0];
    dp[s][3] = find_min(dp[s][3], dp[s][1]);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> D[i];
    for(int i=0; i<m; i++){
        int a, b; cin >> a >> b;
        adj[a].pb(b); adj[b].pb(a);
    }
    vector<int> v;
    for(int i=1; i<=n; i++){
        if(!vis[i]){
            dfs(i, 0);
            v.pb(i);
        }
    }
    vector<int> ans = {0};
    for(auto i: v){
        ans = combine(ans, dp[i][3]);
    }
    int q; cin >> q;
    while(q--){
        int r; cin >> r;
        int L = 2, R = n;
        int t = 0;
        while(L <= R){
            int mid = (L+R)/2;
            if(ans[mid] <= r){
                t = mid;
                L = mid+1;
            }
            else R = mid-1;
        }
        cout << t << "\n";
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10584 KB Output is correct
2 Correct 17 ms 15964 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10584 KB Output is correct
2 Correct 17 ms 15964 KB Output is correct
3 Correct 38 ms 17748 KB Output is correct
4 Correct 46 ms 15308 KB Output is correct
5 Correct 33 ms 12888 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2652 KB Output is correct
2 Correct 22 ms 2392 KB Output is correct
3 Correct 23 ms 2896 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10584 KB Output is correct
2 Correct 17 ms 15964 KB Output is correct
3 Correct 38 ms 17748 KB Output is correct
4 Correct 46 ms 15308 KB Output is correct
5 Correct 33 ms 12888 KB Output is correct
6 Correct 23 ms 2652 KB Output is correct
7 Correct 22 ms 2392 KB Output is correct
8 Correct 23 ms 2896 KB Output is correct
9 Correct 32 ms 3416 KB Output is correct
10 Correct 26 ms 3676 KB Output is correct
11 Correct 26 ms 3156 KB Output is correct