Submission #1176073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176073		HasanV11010238	Džumbus (COCI19_dzumbus)	C++20	110 / 110	82 ms	40520 KiB

dzumbus

#include "bits/stdc++.h"
#define ll long long
#define INF 1000000000000000
using namespace std;
vector<vector<vector<ll>>> dp;
vector<vector<int>> v;
vector<ll> vis, co;
void dfs(int x){
    vis[x] = 1;
    dp[x] = {{0, co[x], INF}, {INF, INF, INF}};
    for (auto el : v[x]){
        if (vis[el] == 1) continue;
        dfs(el);
        int n1 = dp[x].size(), n2 = dp[el].size();
        vector<vector<ll>> ndp(n1 + n2, vector<ll>(3, INF));
        for (int i = 0; i < n1; i++){
            for (int j = 0; j < n2; j++){
                ll mii = min(dp[el][j][0], min(dp[el][j][1], dp[el][j][2]));
                for (int k = 0; k < 3; k++){
                    ndp[i + j][k] = min(dp[x][i][k] + mii, ndp[i + j][k]);
                }
                for (int k1 = 1; k1 < 3; k1++){
                    for (int k2 = 1; k2 < 3; k2++){
                        int ad = 4 - k1 - k2;
                        if (i + j + ad >= n1 + n2) continue;
                        ndp[i + j + ad][2] = min(dp[x][i][k1] + dp[el][j][k2], ndp[i + j + ad][2]);
                    }
                }
            }
        }
        dp[x] = ndp;
    }
    for (int i = 0; i < dp[x].size(); i++){
        dp[x][i][0] = min(dp[x][i][0], dp[x][i][1]);
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, m, a, b;
    cin>>n>>m;
    vis.assign(n + 1, 0), co.assign(n + 1, INF);
    v.assign(n + 1, vector<int>());
    dp.assign(n + 1, vector<vector<ll>>());
    for (int i = 1; i <= n; i++){
        cin>>co[i];
        v[0].push_back(i);
    }
    for (int i = 0; i < m; i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(0);
    vector<ll> so;
    ll pr = INF;
    for (int i = n; i >= 0; i--){
        pr = min(pr, min(dp[0][i][0], min(dp[0][i][1], dp[0][i][2])));
        so.push_back(pr);
    }
    reverse(so.begin(), so.end());
    int q;
    cin>>q;
    while (q--){
        cin>>a;
        int l = 0, r = n, best = -1;
        while (l <= r){
            int mid = (l + r) / 2;
            if (so[mid] <= a){
                best = mid;
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        cout<<best<<"\n";
    }
}

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