Submission #1166587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166587		dosts	Džumbus (COCI19_dzumbus)	C++20	0 / 110	16 ms	8000 KiB

dzumbus

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sp << " " << 
using namespace std;

const int N = 10001,MOD = 998244353,inf = 1e18;

vi sz(N,0),c(N),d(N);
vi edges[N];
vi dp[N],dp2[N];
void dfs(int node,int p) {
    sz[node] = 1;
    dp[node] = {inf,c[node]};
    dp2[node] = {0,c[node]};
    for (auto it : edges[node]) {
        if (it == p) continue;
        dfs(it,node);
        while (dp[node].size() < sz[node]+sz[it]+1) dp[node].push_back(inf);
        while (dp2[node].size() < sz[node]+sz[it]+1) dp2[node].push_back(inf);
        vi dpp = dp[node],dppp = dp2[node];
        for (int j = 0;j<=sz[node];j++) {
            for (int k = 1;k<=sz[it];k++) {
                if (dp[it][k] == inf && dp2[it][k] == inf) continue;
                if (k == 1 || j == 1) {
                    if (j == 1 && k) dp[node][j+k] = min(dp[node][j+k],dpp[j]+dp[it][k]);
                    if (k == 1 && j) dp[node][j+k] = min(dp[node][j+k],dpp[j]+dp[it][k]);
                }
                else {
                    dp[node][j+k] = min(dp[node][j+k],dpp[j]+min(dp2[it][k],dp[it][k]));
                    dp2[node][j+k] = min(dp2[node][j+k],dppp[j]+min(dp2[it][k],dp[it][k]));
                }
            }
        }
        dp[it].clear();
        dp2[it].clear();
        sz[node]+=sz[it];
    }
}

void solve() {
    int n,m;
    cin >> n >> m;
    for (int i=1;i<=n;i++) cin >> c[i];
    for (int i=1;i<n;i++) {
        int a,b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    dfs(1,1);
    int q;
    cin >> q;
    while (q--) {
        int b;
        cin >> b;
        for (int i = n;i>=0;i--) {
            if (i == 1) continue;
            if (min(dp[1][i],dp2[1][i]) <= b) {
                cout << i << '\n';
                break;
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
} 

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